It is currently Sat Sep 21, 2019 7:18 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 31 posts ]  Go to page Previous  1, 2, 3  Next
Author Message
PostPosted: Tue May 07, 2019 3:56 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7582
Location: Canada
dougeff wrote:
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.


Top
 Profile  
 
PostPosted: Tue May 07, 2019 5:09 pm 
Offline
User avatar

Joined: Fri May 08, 2015 7:17 pm
Posts: 2564
Location: DIGDUG
I understand it. I just don't use it.

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

Your needs might differ.

_________________
nesdoug.com -- blog/tutorial on programming for the NES


Top
 Profile  
 
PostPosted: Wed May 08, 2019 11:28 am 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7582
Location: Canada
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.


Top
 Profile  
 
PostPosted: Wed May 08, 2019 11:54 am 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7741
Location: Chexbres, VD, Switzerland
rainwarrior wrote:
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.


Top
 Profile  
 
PostPosted: Wed May 08, 2019 12:27 pm 
Online

Joined: Sun Apr 13, 2008 11:12 am
Posts: 8568
Location: Seattle
Bregalad wrote:
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


Top
 Profile  
 
PostPosted: Wed May 08, 2019 1:14 pm 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7741
Location: Chexbres, VD, Switzerland
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.


Top
 Profile  
 
PostPosted: Wed May 08, 2019 1:19 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7582
Location: Canada
Bregalad wrote:
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.

Bregalad wrote:
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.

Bregalad wrote:
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.

Bregalad wrote:
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.

Bregalad wrote:
...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.


Top
 Profile  
 
PostPosted: Wed May 08, 2019 2:29 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 21595
Location: NE Indiana, USA (NTSC)
Bregalad wrote:
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.

_________________
Pin Eight | Twitter | GitHub | Patreon


Top
 Profile  
 
PostPosted: Thu May 09, 2019 12:39 am 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7741
Location: Chexbres, VD, Switzerland
Quote:
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.


Top
 Profile  
 
PostPosted: Thu May 09, 2019 3:00 pm 
Offline

Joined: Fri Feb 24, 2012 12:09 pm
Posts: 1009
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:
;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).

_________________
homepage - patreon


Top
 Profile  
 
PostPosted: Thu May 09, 2019 3:55 pm 
Offline

Joined: Thu Apr 18, 2019 9:13 am
Posts: 161
nocash wrote:
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.


Top
 Profile  
 
PostPosted: Thu May 09, 2019 6:38 pm 
Offline
User avatar

Joined: Fri May 08, 2015 7:17 pm
Posts: 2564
Location: DIGDUG
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.

_________________
nesdoug.com -- blog/tutorial on programming for the NES


Top
 Profile  
 
PostPosted: Thu May 09, 2019 6:39 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7582
Location: Canada
nocash wrote:
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:
typedef unsigned int uint;


Last edited by rainwarrior on Thu May 09, 2019 6:58 pm, edited 1 time in total.

Top
 Profile  
 
PostPosted: Thu May 09, 2019 6:57 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 21595
Location: NE Indiana, USA (NTSC)
rainwarrior wrote:
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.

_________________
Pin Eight | Twitter | GitHub | Patreon


Top
 Profile  
 
PostPosted: Thu May 09, 2019 8:04 pm 
Offline

Joined: Fri Feb 24, 2012 12:09 pm
Posts: 1009
rainwarrior wrote:
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).

_________________
homepage - patreon


Last edited by nocash on Thu May 09, 2019 8:11 pm, edited 1 time in total.

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 31 posts ]  Go to page Previous  1, 2, 3  Next

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 6 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group