CMP setting N flag when it shouldn't?

[rainwarrior]

My opinion is that bit shifting only makes sense for unsigned numbers.

Even with the floor behaviour on signed numbers, that's still useful for many purposes just by itself. What makes sense or not is how you apply it.

Whether you need round toward zero depends on the situation. It might be what you expect for division on signed numbers, as it is the default in several programming languages, and is how we might truncate a written decimal number.


If you want the negative and positive to be symmetrical, you want round toward zero. On 6502 that means signed division is more expensive, requiring a few more operations, but that's true of so many of its signed operations.

If you want a continuous modulo across positive and negative space, you want round down instead. In some cases, this may also help balance rounding errors and increase numerical stability, e.g. if generating a sine wave this way, negative rounding errors may cancel positive rounding errors in a way they wouldn't if you had rounded toward zero.

In other cases the rounding error is small enough to be unimportant, and you might just go with whatever's fastest. In this case, you can probably accept the round down behaviour for efficiency's sake. (On a ones' complement platform, round to zero might be faster.)



There's a time and place for both of these behaviours. Both of them make sense, but I think the round down behaviour is a little bit unexpected when you're used to round to zero (C, C++, x86 IDIV, etc.). I know I didn't think of it right away.

[dougeff]

I understand it. I just don't use it.

For me, the way I code, it doesn't make sense.

Your needs might differ.

[rainwarrior]

Maybe also worth noting that a left shift (i.e. multiply by 2) doesn't have this ambiguity.

<< 1 is x 2 for both positive and negative, unsigned and signed numbers alike.

[Bregalad]

Maybe also worth noting that a left shift (i.e. multiply by 2) doesn't have this ambiguity.

<< 1 is x 2 for both positive and negative, unsigned and signed numbers alike.

Are you kiding ? If you shift a negative number left, you'll get a completely wrong resut if it's not adjusted. Even if the result is adjusted, you have to be watchful for all overflows and bits shifting into the sign bit in all cases.

[lidnariq]

Are you kiding ? If you shift a negative number left, you'll get a completely wrong resut if it's not adjusted. Even if the result is adjusted, you have to be watchful for all overflows and bits shifting into the sign bit in all cases.

Overflow is exactly equally as problematic regardless of whether the number is signed or unsigned.

(all 8 bit types:)
-120 << 1 = 16
136 << 1 = 16
-30 << 1 = -60

[Bregalad]

Sure, but the thing is that overflow can not only give a wrong result, but also with the wrong sign, which is tricky.
Also, this is why there's no difference between arithmetic shift left and logical shift left. I wonder why the 6502's instruction is called ASL and not LSL since the latter would be the same but be more symetrical to LSR. Oh well.

[rainwarrior]

Are you kiding ?

No. ?

If the result of the multiply fits in the range of the number, the left shift is a valid x2.

Otherwise there's no possible valid result. Overflow. That's completely normal. Same problem applies to unsigned multiply.

If you shift a negative number left, you'll get a completely wrong resut if it's not adjusted.

What does "adjusted" mean? Unlike shifting right, there is no loss of precision from rounding. A left shift bringing in a zero is a multiply by 2 in two's complement.

you have to be watchful for all overflows and bits shifting into the sign bit in all cases.

No, you only get an invalid sign bit in the overflow case. In all other cases, the sign bit remains valid.

For overflow, you have to be as watchful for that whether it's signed or unsigned.

Sure, but the thing is that overflow can not only give a wrong result, but also with the wrong sign, which is tricky.

Well, if you're trying to detect overflow at runtime, signed is slightly different. Before doing the shift, the overflow indication would be XOR of the top 2 bits, rather than just the top 1 bit for unsigned. Kinda similar to the signed comparison requiring 2 bits of info.

Otherwise you can prevent overflow by knowing your ranges and keeping the numbers small enough, but that principle is the same for unsigned.

...this is why there's no difference between arithmetic shift left and logical shift left.

Yes. This is very strongly correlated with the fact that <<1 is x2 for both unsigned and signed.

[tepples]

Also, this is why there's no difference between arithmetic shift left and logical shift left. I wonder why the 6502's instruction is called ASL and not LSL since the latter would be the same but be more symetrical to LSR. Oh well.

Zilog Z80 has a "logical shift left" at CB 60 through CB 67 that's like SCF then RL (or like SEC then ROL in 6502 syntax). This turned out not to be very useful, so Sharp replaced it in the SM83 (8080-inspired CPU core used in Game Boy's LR35902 SOC and some 8-bit MCUs) with a "swap nibbles" instruction.

[Bregalad]

What does "adjusted" mean? Unlike shifting right, there is no loss of precision from rounding. A left shift bringing in a zero is a multiply by 2 in two's complement.

Oh sorry I confused with shifting right... oh well. I'm getting old guys.

[nocash]

I wasn't aware of the different rounding for signed divide vs signed shift right. But I think that I do now understand why disassembled C code is so crappy!

In ASM code, almost everything is almost always unsigned (eg. memory addresses, loop counters, tile numbers, and so on). In most cases it really doesn't make sense to use signed numbers (and least to shift or divide them).

For C programmers, the main difference between "int" and "uint" is probably that "int" is shorter (and easier to pronounce). And so they might end up with signed "int", without actually being aware of what they are doing (and what the compiler will do if they use a supposedly harmless expression like "i/32" instead of right shifting).

For the example, the 3DS bootrom has some interrupt handling code like this:

Code: Select all

;in:  r4 = irq.no (range 0..7Fh)
;out: r3 = address of 32bit word: (17E01200h+(irq.no/20h*4))
;out: r1 = bit number within 32bit word: (irq.no AND 1Fh)
;---
0001247C 17E1     asrs    r1,r4,1Fh    ;sign-bit of irq.no
0001247E 4B0B     ldr     r3,=17E01200h
00012480 0EC9     lsrs    r1,r1,1Bh    ;sign*1Fh (=00h or 1Fh)
00012482 1909     adds    r1,r1,r4     ;irq.no + sign*1Fh
00012484 114A     asrs    r2,r1,5h     ;irq.no/20h
00012486 0949     lsrs    r1,r1,5h     ;irq.no/20h
00012488 0092     lsls    r2,r2,2h     ;irq.no/20h*4
0001248A 0149     lsls    r1,r1,5h     ;irq.no/20h*20h
0001248C 1A61     subs    r1,r4,r1     ;irq.no - (irq.no/20h*20h)  ;aka AND 1Fh
0001248E 18D3     adds    r3,r2,r3     ;17E01200h + (irq.no/20h*4)

The compiler did apparently try to optimize "div 20h" as "shift 5", but then it went amok on rounding the (un-)signed result towards zero.
The code would be probably twice as small if the programmer had declared r4 as unsigned value (or if the source code had used shift instead of divide).

Assuming that it's a pretty common problem, and that it's impossible to teach C programmers not to use signed numbers... it would almost make sense to implement a "shift-and-round-towards-zero" opcode in newer processors (the newer ARM CPUs do actually have a fairly useless "uxt" opcode which helps on similar compiler-world issues, eg. when compilers think that they must ensure that "mov r0,15h" won't exceed FFFFh; which usually requires two useless opcodes, but can be now replaced with only one useless opcode).

[supercat]

Assuming that it's a pretty common problem, and that it's impossible to teach C programmers not to use signed numbers... it would almost make sense to implement a "shift-and-round-towards-zero" opcode in newer processors (the newer ARM CPUs do actually have a fairly useless "uxt" opcode which helps on similar compiler-world issues, eg. when compilers think that they must ensure that "mov r0,15h" won't exceed FFFFh; which usually requires two useless opcodes, but can be now replaced with only one useless opcode).

What's really needed is a usable replacement for C which includes integer types with better semantics. Python, IMHO, did things properly, using separate operators for floating-point division (which converts any operand type to a floating-point number) and integer division (which rounds negative) but it's not really suitable for low-level tasks. In several decades of programming, I can only think of one time when truncating division would have been useful for a negative divisor, and on that occasion (targeting a Z80) the compiler handled it sufficiently slowly that I had to use a manually-rounded shift anyway.

[dougeff]

I've been trying to learn C# lately. After writing some functional code, I thought to myself "maybe I should just replace all the int's with uint, it should run faster"

Then I got about a dozen error messages. It seems that most of the system's functions expect signed int... and simply can't handle a uint, for some reason.

[rainwarrior]

Assuming that it's a pretty common problem, and that it's impossible to teach C programmers not to use signed numbers... it would almost make sense to implement a "shift-and-round-towards-zero" opcode in newer processors (the newer ARM CPUs do actually have a fairly useless "uxt" opcode which helps on similar compiler-world issues, eg. when compilers think that they must ensure that "mov r0,15h" won't exceed FFFFh; which usually requires two useless opcodes, but can be now replaced with only one useless opcode).

Why do you think C programmers are uncomfortable with unsigned numbers? For high performance code, it's probably normal to go unsigned by default? That was one of the first things I saw in internal coding guides when I started working professionally.

Though honestly, this entire problem only happens with division. ...and it doesn't even happen on x86, because it's IDIV instruction is already round to zero.

Actually technically the C spec allows signed division rounding to be implementation defined, so even the ARM compiler you were using could have rounded down if it wanted. Though, TBH, it's probably a good idea that it doesn't, since I think prevailing common expectation is to round to zero. C++11 decided to define it to finally define it as round to zero, BTW, but it has more or less been the de-facto standard for a long time.

(Technically even signed by default is implementation defined. cc65 defines default char as unsigned, for example. It's rare to see this in practice though.)

Also, aside from typing "unsigned" being a really simple available solution... if you don't like typing it, there's a really simple solution for that too:

Code: Select all

typedef unsigned int uint;

[tepples]

Though honestly, this entire problem only happens with division.

That and the general trend of newer versions of C and C++ compilers becoming more pedantic about treating signed overflow and other undefined behaviors as an excuse to make unexpectedly aggressive optimizations. Raymond Chen has referred to this aggression as "time travel". Unsigned addition, subtraction, and multiplication, on the other hand, are carefully defined to wrap around modulo [type]_MAX + 1.

[nocash]

even the ARM compiler you were using could have rounded down if it wanted.

Hell, no, I wasn't using a compiler, not me. The disassembly was from Nintendo's boot rom. I am not writing that kind of code, what do think?
I didn't knew that there coding guides recommending to use unsigned numbers in professional C code, that's a good thing. Apparently not everyone at Nintendo did read those guides.
The problem isn't division as such. The problem is replacing signed division by shifting (particulary when you have a number that is never negative, and the compilier is nethertheless producing nonsense code for handling the sign bit).