16 Bit, Fixed Point, Signed Arithmetic

16 Bit, Fixed Point, Signed Arithmetic
by Guilty on 2016-09-16 (#179621)

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:

  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:

  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:

  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?

Re: 16 Bit, Fixed Point, Signed Arithmetic
by calima on 2016-09-16 (#179622)

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

Re: 16 Bit, Fixed Point, Signed Arithmetic
by Bregalad on 2016-09-16 (#179623)

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.

Re: 16 Bit, Fixed Point, Signed Arithmetic
by lazigamer on 2016-09-16 (#179624)

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:

  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

Re: 16 Bit, Fixed Point, Signed Arithmetic
by thefox on 2016-09-16 (#179625)

Guilty 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.)

(BTW, it's two's complement, not compliment.

)

Re: 16 Bit, Fixed Point, Signed Arithmetic
by dougeff on 2016-09-16 (#179628)

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=subpixel&start=15#p165221

Code:

   lda lowbyte
   asl
   lda highbyte
   adc #$00

Re: 16 Bit, Fixed Point, Signed Arithmetic
by Guilty on 2016-09-16 (#179643)

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:

  lda value
  eor #$FF
  clc
  adc #$01
  sta value

but to negate a SIXTEEN bit value it would be

Code:

  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.

Re: 16 Bit, Fixed Point, Signed Arithmetic
by rainwarrior on 2016-09-16 (#179645)

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

Code:

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

Re: 16 Bit, Fixed Point, Signed Arithmetic
by rainwarrior on 2016-09-16 (#179646)

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

Code:

; 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.

Re: 16 Bit, Fixed Point, Signed Arithmetic
by Guilty on 2016-09-16 (#179660)

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:

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