16 Bit, Fixed Point, Signed Arithmetic

Are you new to 6502, NES, or even programming in general? Post any of your questions here. Remember - the only dumb question is the question that remains unasked.

Moderator: Moderators

Post Reply
User avatar
Guilty
Posts: 93
Joined: Fri Apr 08, 2016 5:58 pm
Location: California, USA

16 Bit, Fixed Point, Signed Arithmetic

Post by Guilty » Fri Sep 16, 2016 1:23 am

I'm trying to implement some really basic physics into my game and I'm coming up with some interesting problems I've never thought of before.

My objects have 16 bit fixed point coordinates; that's a byte of pixel positioning and a byte of subpixel positioning. Simple enough. My objects also have 16 bit fixed point velocities, but those values are signed. This is very simple when it comes to applying the most significant byte of the velocity to the most significant byte of the coordinate:

Code: Select all

  lda OBJHIH,x ;load this OBJect's HI byte for Horizontal velocity
  clc
  adc OBJHIX,x ;add it to this OBJect's HI byte for the X coordinates
  sta OBJHIX,x ;store result
Coders familiar with 2's compliment notation will see that negative velocities are already being handled.

I've also expanded on this to handle the subpixel velocity:

Code: Select all

  lda OBJHIH,x ;load this OBJect's HI byte for Horizontal velocity
  clc
  adc OBJHIX,x ;add it to this OBJect's HI byte for the X coordinates
  sta OBJHIX,x ;store result

  lda OBJLOH,x ;lo byte of horizontal velocity
  clc
  adc OBJLOX,x
  bcc .carryHandled
  inc OBJHIX,x
.carryHandled
Simple enough, I'm just adding the low byte of the horizontal velocity onto the subpixel X coordinates, and then adding the carry onto the pixel X coordinates. But this doesn't handle negative cases, so we must expand further:

Code: Select all

  lda OBJHIH,x ;load this OBJect's HI byte for Horizontal velocity
  clc
  adc OBJHIX,x ;add it to this OBJect's HI byte for the X coordinates
  sta OBJHIX,x ;store result

  lda OBJHIH,x			;negative flag set if our horizontal velocity is negative
  php				      ;store the negative flag
  lda OBJLOX,x
  plp				      ;pull negative flag
  bmi .HNeg			   ;branch on negative
  clc
  adc OBJLOH,x
  bcc .PosCarryHandled
  inc OBJHIX,x			;increase the pixel x coordinate if we overflowed subpixels
.PosCarryHandled
  jmp .HLoDone
.HNeg
  sec
  sbc OBJLOH,x
  bcc .NegCarryHandled
  dec OBJHIX,x			;DEcrease the pixel x coordinate if we UNDERflowed subpixels
.NegCarryHandled
.HLoDone
  sta OBJLOX,x
This works. If the character's velocity is $01.80 (1.5), he will advance 3 pixels to the right every two frames. If the character's velocity is $FF.80(-1.5), he will advance 3 pixels to the left every two frames.
But I don't think there's a way to express a number between 0 and -1 under this system. I can't conceive of any other way to do this, either. Is this an entirely flawed approach? Anyone have any sage advice?

calima
Posts: 1160
Joined: Tue Oct 06, 2015 10:16 am

Re: 16 Bit, Fixed Point, Signed Arithmetic

Post by calima » Fri Sep 16, 2016 1:41 am

Cheat, write it in C and see what cc65 outputs?

User avatar
Bregalad
Posts: 7892
Joined: Fri Nov 12, 2004 2:49 pm
Location: Chexbres, VD, Switzerland

Re: 16 Bit, Fixed Point, Signed Arithmetic

Post by Bregalad » Fri Sep 16, 2016 1:52 am

calima wrote:Cheat, write it in C and see what cc65 outputs?
Terrible idea, considering how unoptimized and messy the assembly cc65 outputs.

Personally what I'm doing with 16-bit coordinates is that I use the middle 8 bits for pixel position, and the low 4 bits for sub-pixel position. The upper 4 bits are there just for overflow detection, but could be used for position among 8 or 16 screens later if there was such a need.

lazigamer
Posts: 23
Joined: Mon Oct 10, 2011 9:05 am

Re: 16 Bit, Fixed Point, Signed Arithmetic

Post by lazigamer » Fri Sep 16, 2016 2:03 am

If I understand what you are doing, adding two 8.8 fixed point variables together is the same as adding any two 16-bit variables. The increment instruction does not need to be used. This the necessary code.

Code: Select all

  lda OBJLOX,x	;add low byte of horizontal velocity to low byte of X coordinate
  clc
  adc OBJLOH,x
  sta OBJLOX,x	;store variable back

  lda OBJHIX,x	;add high byte of horizontal velocity to high byte of X coordinate, carry is added too
  adc OBJHIH,x
  sta OBJHIX,x	;store variable back

User avatar
thefox
Posts: 3141
Joined: Mon Jan 03, 2005 10:36 am
Location: Tampere, Finland
Contact:

Re: 16 Bit, Fixed Point, Signed Arithmetic

Post by thefox » Fri Sep 16, 2016 2:56 am

Guilty wrote:This works. If the character's velocity is $01.80 (1.5), he will advance 3 pixels to the right every two frames. If the character's velocity is $FF.80(-1.5), he will advance 3 pixels to the left every two frames.
But I don't think there's a way to express a number between 0 and -1 under this system. I can't conceive of any other way to do this, either. Is this an entirely flawed approach? Anyone have any sage advice?
Your problem is that you're using $FF.80 to represent -1.5, when in fact it should be $FE.80. (Negate $01.80.)

(BTW, it's two's complement, not compliment. :))
Download STREEMERZ for NES from fauxgame.com! — Some other stuff I've done: fo.aspekt.fi

User avatar
dougeff
Posts: 2712
Joined: Fri May 08, 2015 7:17 pm
Location: DIGDUG
Contact:

Re: 16 Bit, Fixed Point, Signed Arithmetic

Post by dougeff » Fri Sep 16, 2016 3:12 am

Use 16 bit movement and position math, as you originally described. (The second block of code in OP) It DOES handle negative cases.

(Pixel 8 bit, Subpixel 8 bit)

Then add 00,80 and use the upper byte for final onscreen coordinates. (to account for rounding errors)

Or, instead of adding 00,80, use tokumaru's suggestion from here...
viewtopic.php?f=2&t=12434&hilit=subpixe ... 15#p165221

Code: Select all

   lda lowbyte
   asl
   lda highbyte
   adc #$00
nesdoug.com -- blog/tutorial on programming for the NES

User avatar
Guilty
Posts: 93
Joined: Fri Apr 08, 2016 5:58 pm
Location: California, USA

Re: 16 Bit, Fixed Point, Signed Arithmetic

Post by Guilty » Fri Sep 16, 2016 2:03 pm

Bregalad wrote:Personally what I'm doing with 16-bit coordinates is that I use the middle 8 bits for pixel position, and the low 4 bits for sub-pixel position. The upper 4 bits are there just for overflow detection, but could be used for position among 8 or 16 screens later if there was such a need.
That's a really neat system and I will need to consider using it. Right now I'm using a separate byte when it comes to multi-screen positioning, whose first 4 bits are horizontal screen lengths and whose last 4 bits are vertical screen lengths.
lazigamer wrote:If I understand what you are doing, adding two 8.8 fixed point variables together is the same as adding any two 16-bit variables.
I don't think this is the case. The 16 bit value that I'm adding is a signed value, and the sign bit is only in the high byte. That means that simply adding the low byte of the velocity to the low byte of the positioning won't always be correct. At the very least, when I implemented that it gave me unexpected results that pointed to my conclusion here.
thefox wrote:Your problem is that you're using $FF.80 to represent -1.5, when in fact it should be $FE.80. (Negate $01.80.
THIS tells me what I'm doing wrong! I was implementing two's compli complement incorrectly. To negate an eight bit value it's the simple

Code: Select all

  lda value
  eor #$FF
  clc
  adc #$01
  sta value
but to negate a SIXTEEN bit value it would be

Code: Select all

  lda valueHigh
  eor #$FF
  sta valueHigh
  lda valueLow
  eor #$FF
  clc
  adc #$01
  sta valueLow
which is a really important distinction. I've got it all working now! I'm gonna spend some time now to try and make the routine branch less.

User avatar
rainwarrior
Posts: 7824
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: 16 Bit, Fixed Point, Signed Arithmetic

Post by rainwarrior » Fri Sep 16, 2016 2:12 pm

You're missing the carry there. If the low value rolls over, you need to propagate the carry to increment high byte too.

Code: Select all

  lda valueLow
  eor #$FF
  clc
  adc #<$0001
  sta valueLow
  lda valueHigh
  eor #$FF
  adc #>$0001
  sta valueHigh

User avatar
rainwarrior
Posts: 7824
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: 16 Bit, Fixed Point, Signed Arithmetic

Post by rainwarrior » Fri Sep 16, 2016 2:15 pm

It might be faster or smaller just to subtract from 0 in these cases:

Code: Select all

; 16 bit
lda #0
sec
sbc valueLow
sta valueLow
lda #0
sbc valueHigh
sta valueHigh

; 8 bit
lda #0
sec
sbc value
sta value
Trying to do it with EOR is more applicable when your value is already in A.

User avatar
Guilty
Posts: 93
Joined: Fri Apr 08, 2016 5:58 pm
Location: California, USA

Re: 16 Bit, Fixed Point, Signed Arithmetic

Post by Guilty » Fri Sep 16, 2016 8:19 pm

rainwarrior wrote:You're missing the carry there.
Good catch, and thank you.
rainwarrior wrote:It might be faster or smaller just to subtract from 0 in these cases:
...
Trying to do it with EOR is more applicable when your value is already in A.
And thanks for that as well! That might speed up my metasprite routines a little, if I can apply it as such.

Also, Dougeff and Lazigamer are completely right and I'm making mountains of molehills. This routine works perfectly as far as I've tested:

Code: Select all

  clc
  lda OBJLOX,x
  adc OBJLOH,x
  sta OBJLOX,x
  
  lda OBJHIX,x
  adc OBJHIH,x
  sta OBJHIX,x

Post Reply