please help me with fixed-point math

« previous next »

Print

Pages: [1] 2 Go Down

Author Topic: please help me with fixed-point math (Read 9967 times)

0 Members and 2 Guests are viewing this topic.

ben_g

Hey cool I can set a custom title now :)
LV9 Veteran (Next: 1337)
Posts: 1002
Rating: +125/-4
Asm noob

please help me with fixed-point math

« on: May 20, 2011, 05:22:57 pm »

Hi,
I am trying to port a simple 3D engine from GML to z80, but I can't get it to work
I think my fixed-point math routines aren't doing what they are supposed to do. Can enybody please help with that?

This is what it should do:

(speed so low becouse of the recording software. The engine itself renders very efficiently)

And what i got is just an emty screen, while the camera is 5 units away, facing the target, and everything between 1 and 256 units should be visible.

The math currently being unsigned might be one problem, but i couldn't find any 16bit signed fixed-point routines with google.

Spoiler For assembly InitView routine:

Spoiler For assembly 3DTo2D routine:

Spoiler For assembly math routines:

Has enybody got some routines for this on their hard drive (you will get credits for it) or can enybody gelp me with writing my own?

BTW: I added the exe for if enybody wants to try the engine itself (sorry for the ones withouth windows, but GM can only compile exe's)

EDIT: I forgot to say the controls: use z, q, s and d to walk and turn

engine.exe (2283.79 kB - downloaded 300 times.)

« Last Edit: May 23, 2011, 01:52:29 pm by ben_g »

Logged

My projects
- The Lost Survivors (Unreal Engine) ACTIVE [GameCommandoSquad main project]
- Oxo, with single-calc multiplayer and AI (axe) RELEASED (screenshot) (topic)
- An android version of oxo (java) ACTIVE
- A 3D collision detection library (axe) RELEASED! (topic)(screenshot)(more recent screenshot)(screenshot of it being used in a tilemapper)

Spoiler For inactive:

This signature was last updated on 20/04/2015 and may be outdated

ben_g

Hey cool I can set a custom title now :)
LV9 Veteran (Next: 1337)
Posts: 1002
Rating: +125/-4
Asm noob

Re: please help me with fixed-point math

« Reply #1 on: May 21, 2011, 06:36:57 pm »

Isn't there anybody who can help me with fixed-point math? I can't find anything useful on google, but I think that almost every advanced asm programmer has used fixed-point math.

Or is everybody just to busy with the axe programming competition so that nobady has time to help other people?

« Last Edit: May 21, 2011, 06:37:35 pm by ben_g »

Logged

My projects
- The Lost Survivors (Unreal Engine) ACTIVE [GameCommandoSquad main project]
- Oxo, with single-calc multiplayer and AI (axe) RELEASED (screenshot) (topic)
- An android version of oxo (java) ACTIVE
- A 3D collision detection library (axe) RELEASED! (topic)(screenshot)(more recent screenshot)(screenshot of it being used in a tilemapper)

Spoiler For inactive:

This signature was last updated on 20/04/2015 and may be outdated

thepenguin77

z80 Assembly Master
LV10 31337 u53r (Next: 2000)
Posts: 1594
Rating: +823/-5
The game in my avatar is bit.ly/p0zPWu

Re: please help me with fixed-point math

« Reply #2 on: May 22, 2011, 12:49:36 am »

Sorry, I haven't really been in the helping mood lately. I've been busy with my own stuff, so debugging faulty code that wasn't even written by me can just be annoying.

For 8.8 bit math, your best bet is just to use standard 16x16 bit routines and then adjust the output accordingly.

So multiplying two numbers together. 8.8 * 8.8 = 88.88. Depending on how much precision you need, you can either just take the whole part, or take both the whole part and the decimal.

From wikiTi:

mult_de_bc
   ld	hl, 0

   sla	e		; optimised 1st iteration
   rl	d
   jr	nc, $+4
   ld	h, b
   ld	l, c

   ld	a, 15
_loop:
   add	hl, hl
   rl	e
   rl	d
   jr	nc, $+6
   add	hl, bc
   jr	nc, $+3
   inc	de
   
   dec	a
   jr	nz, _loop
   
   ret

So for this routine. DE would end up being your new whole part and HL would be your new decimal part.

Division is similar. 8.8/8.8=8888. Now, you can't immediately get the decimal out of this one, but you have to remember that the division routines also return the remainder, which, if you divide that by the same number again, will get you the decimal.

Again, from wikiTi:

div_ac_de:
   ld	hl, 0
   ld	b, 16

_loop:
   sll	c
   rla
   adc	hl, hl
   sbc	hl, de
   jr	nc, $+4
   add	hl, de
   dec	c
   
   djnz	_loop
   
   ret

So this returns with AC = the whole part, and HL = remainder. So just divide HL by your original DE again to get the first two bytes of your decimal.

Edit:
Oooo, your 16 bit math routines aren't going to work at all. You have to remember that the upper and lower bits are dependent of each other. Just think of them like a two digit number. Try adding 15+36.

The right way: 6+5=11 carry the one: 1+1+3=5. So bring it together: 51

But your way: 6+5=11 don't carry the one: 1+3=4. So together: 41

This is the general concept that is making them not work, your subtract, add, and multiply functions suffer this problem, but your divide works though because it relies on an entirely different principle.

« Last Edit: May 22, 2011, 12:56:24 am by thepenguin77 »

Logged

zStart v1.3.013 9-20-2013

All of my utilities
TI-Connect Help
You can build a statue out of either 1'x1' blocks or 12'x12' blocks. The 1'x1' blocks will take a lot longer, but the final product is worth it.
-Runer112

ben_g

Hey cool I can set a custom title now :)
LV9 Veteran (Next: 1337)
Posts: 1002
Rating: +125/-4
Asm noob

Re: please help me with fixed-point math

« Reply #3 on: May 22, 2011, 01:25:12 pm »

I already thought my routines weren't working

But I don't really understand what's wrong with my addition. It relies on the principle that a/255 + b/255 = (a+b)/255, so just using 'add' to add the numbers as 16bit integers should work, or am I totally wrong with this?

And the Multiplication: (a/255)*(b/255) = a*b, so shifting 8 bits left should give (a*b)/255, so calculating the 32bit result and using bit 8-24 should provide the result, or is this wrong again? Maybe i just don't understand fixed-point numbers correctelly

What I said earlier is not becouse I don't believe you, I just want to know why it won't work, so that i can avoid it in my other programs.

EDIT: and for the signed part: for the multiplication and division, the sign of the result should be the XOR result of the sign of the 2 arguments, right?

« Last Edit: May 22, 2011, 04:01:01 pm by ben_g »

Logged

My projects
- The Lost Survivors (Unreal Engine) ACTIVE [GameCommandoSquad main project]
- Oxo, with single-calc multiplayer and AI (axe) RELEASED (screenshot) (topic)
- An android version of oxo (java) ACTIVE
- A 3D collision detection library (axe) RELEASED! (topic)(screenshot)(more recent screenshot)(screenshot of it being used in a tilemapper)

Spoiler For inactive:

This signature was last updated on 20/04/2015 and may be outdated

thepenguin77

z80 Assembly Master
LV10 31337 u53r (Next: 2000)
Posts: 1594
Rating: +823/-5
The game in my avatar is bit.ly/p0zPWu

Re: please help me with fixed-point math

« Reply #4 on: May 22, 2011, 07:23:42 pm »

Ok, yes, what you are saying is true. The problem is that when you are working with 16 bit numbers, you are treating them as two sets of 8 bit numbers rather than a set of 16 bit numbers. To demonstrate, I have to go back in math a long time:

Let's say that you need to add two numbers together. Lets say 23 and 69.

     2 3
    +6 9
--------

Adding the ones, you get this:

     2 3
    +6 9
--------
      12

But that won't do, so we have to carry the one:

     1
     2 3
    +6 9
--------
       2

And we finally end up with:

     1
     2 3
    +6 9
--------
     9 2

Now, to put this into bytes: Let's say that you need to add two 16 bit numbers, $5678 and $BCDF. $5678 is two bytes of $56 and $78. So if we convert that to two decimal bytes, we get $5678 = 86 120 and $BCDF = 188 233.

    86 120
  +188 233
----------

We add the first bytes together, just like you do:

    86 120
  +188 233
----------
       353

353 is not going to fit into one byte. So we have to convert that to 97 and carry a 1 to the next byte:

     1
    86 120
  +188 233
----------
        97

So now we add the second bytes:

     1
    86 120
  +188 233
----------
   275  97

But what's that, another overflow:

     1
    86 120
  +188 233
----------
 1  19  97

So we can see here that the final result is actually 3 bytes. What you have to remember is that the bytes are dependent of each other when you are doing math operations on them. The exact same thing I showed here happens in subtraction. And when you multiply or divide two bytes, the results are really wrong because when multiplying two bytes, it looks like this:

$5678 * $BCDF = ($5600 + $78) * ($BC00 + $DF) = ($5600 * $BC00) + ($5600 * $DF) + ($78 * $BC00) + ($78 * $DF)

And then don't forget, when you add these separate operations together, there will probably be some carrying going on.

For signed numbers: first of all, you don't need to worry about them in addition and subtraction because the z80 actually handles it all for you:

;HL + DE

	add	 hl, de

;HL - DE

	or	a	;clear carry flag
	sbc	hl, de

Then for multiplication, before the routine runs, you need to figure out what the sign will be at the end. So 1 * 1 = 1, -1 * 1 = -1, and -1 * -1 = 1. Then convert both of the operands to positive, do the operation, and give the result the proper sign.

Changing the sign is not as simple as just XOR'ing the whole thing with %1111111 11111111. If that was true, -00 would equal FF. So the best way is to make a routine like this:

negHL:
	push	de
	ex	de, hl
	ld	hl, 0
	or	a
	sbc	hl, de
	pop	de
	ret

I use that quite a bit in my math routines.

Logged

+2/-0 karm for this message

zStart v1.3.013 9-20-2013

All of my utilities
TI-Connect Help
You can build a statue out of either 1'x1' blocks or 12'x12' blocks. The 1'x1' blocks will take a lot longer, but the final product is worth it.
-Runer112

calc84maniac

eZ80 Guru
Coder Of Tomorrow
LV11 Super Veteran (Next: 3000)
Posts: 2912
Rating: +471/-17

Re: please help me with fixed-point math

« Reply #5 on: May 22, 2011, 08:45:43 pm »

thepenguin77, here's a more optimized 16-bit negation method (which also works with BC or DE with some modifications)

	xor a
	sub l
	ld l,a
	sbc a,a
	sub h
	ld h,a

Logged

+3/-0 karm for this message

"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman

ben_g

Hey cool I can set a custom title now :)
LV9 Veteran (Next: 1337)
Posts: 1002
Rating: +125/-4
Asm noob

Re: please help me with fixed-point math

« Reply #6 on: May 23, 2011, 03:54:39 pm »

so, will this work as a signed fixed-point division?

DivFP:
  ;IN: hl, de
  ;OUT: hl = hl / de
  bit 7, h
  jr nz, _DivFP_FirstNeg
  bit 7, d
  jr nz, _DivFP_AnsNeg
  jr z, _DivFP_AnsPos
_DivFP_FirstNeg:
  bit 7, h
  jr nz, _DivFP_AnsPos
_DivFP_AnsNeg:
  ld a, 1
  push af
  jr DivFP_Cont
_DivFP_AnsPos:
  ld a, 0
  push af
_DivFP_Cont
  res 7, h
  res 7, d
  ld a, h
  ld h, l
  ld l, 0
  call Div24by16
  pop af
  cp 1
  call z, NegHL
  ret

Div24by16:
  push hl ;INPUTS: ahl = dividend de = divisor	;1
  pop ix ;OUTPUTS: ahl = quotient de = divisor	;0
  ld hl,0
  ld b,24
_Div24by16loop:
  add ix,ix
  rla
  adc hl,hl
  jr c,_Div24by16setbit
  or a
  sbc hl,de
  add hl,de
  jr c,_Div24by16skip
_Div24by16setbit:
  or a
  sbc hl,de
  inc ix
_Div24by16skip:
  djnz _Div24by16loop
  push ix			;1
  pop hl			;0
  ret

NegHL:
	xor a
	sub l
	ld l,a
	sbc a,a
	sub h
	ld h,a

Logged

My projects
- The Lost Survivors (Unreal Engine) ACTIVE [GameCommandoSquad main project]
- Oxo, with single-calc multiplayer and AI (axe) RELEASED (screenshot) (topic)
- An android version of oxo (java) ACTIVE
- A 3D collision detection library (axe) RELEASED! (topic)(screenshot)(more recent screenshot)(screenshot of it being used in a tilemapper)

Spoiler For inactive:

This signature was last updated on 20/04/2015 and may be outdated

thepenguin77

z80 Assembly Master
LV10 31337 u53r (Next: 2000)
Posts: 1594
Rating: +823/-5
The game in my avatar is bit.ly/p0zPWu

Re: please help me with fixed-point math

« Reply #7 on: May 23, 2011, 09:22:14 pm »

You need to swap your first bit 7, h and bit 7, d. Then throw a RET at the end of NegHL. But, assuming that that divide routine works, that should give you the right answer.

Logged

zStart v1.3.013 9-20-2013

All of my utilities
TI-Connect Help
You can build a statue out of either 1'x1' blocks or 12'x12' blocks. The 1'x1' blocks will take a lot longer, but the final product is worth it.
-Runer112

ben_g

Hey cool I can set a custom title now :)
LV9 Veteran (Next: 1337)
Posts: 1002
Rating: +125/-4
Asm noob

Re: please help me with fixed-point math

« Reply #8 on: May 25, 2011, 03:19:41 pm »

OK, I swapped it

Will this work as a signed fixed-point divide?

MulFP:
  ;Multiplies 2 16bit fixed-point numbers
  ;IN: de, bc
  ;OUT: de * bc in hl
  ;DESTROYS: 
  bit 7, d
  jr nz, _MulFP_FirstNeg
  bit 7, b
  jr nz, _MulFP_AnsNeg
  jr z, _MulFP_AnsPos
_MulFP_FirstNeg:
  bit 7, b
  jr nz, _MulFP_AnsPos
_MulFP_AnsNeg:
  ld a, 1
  push af
  jr _MulFP_Cont
_MulFP_AnsPos:
  ld a, 0
  push af
_MulFP_Cont
  res 7, b
  res 7, d
  call Mul16  
  ld l, h
  ld h, e
  pop af
  cp 1
  call z, NegHL
  ret

Mul16:     ; DEHL=BC*DE
  ld hl,0
  ld a,16
Mul16Loop:
  add hl,hl
  rl e
  rl d
  jp nc,NoMul16
  add hl,bc
  jp nc,NoMul16
  inc de                         ; This instruction (with the jump) is like an "ADC DE,0"
NoMul16:
  dec a
  jp nz,Mul16Loop
  ret

NegHL:
	xor a
	sub l
	ld l,a
	sbc a,a
	sub h
	ld h,a
	ret

Logged

My projects
- The Lost Survivors (Unreal Engine) ACTIVE [GameCommandoSquad main project]
- Oxo, with single-calc multiplayer and AI (axe) RELEASED (screenshot) (topic)
- An android version of oxo (java) ACTIVE
- A 3D collision detection library (axe) RELEASED! (topic)(screenshot)(more recent screenshot)(screenshot of it being used in a tilemapper)

Spoiler For inactive:

This signature was last updated on 20/04/2015 and may be outdated

thepenguin77

z80 Assembly Master
LV10 31337 u53r (Next: 2000)
Posts: 1594
Rating: +823/-5
The game in my avatar is bit.ly/p0zPWu

Re: please help me with fixed-point math

« Reply #9 on: May 25, 2011, 09:37:05 pm »

Aww... So close. Assuming the Mul16 works, the only problem I see is that you can't make a number positive by just resetting bit 15. You have to use the NegHL on each of them individually. Or make NegDE and NegBC.

-1 = %11111111 11111111
1 = %0000000 00000001

If you just reset bit 15, you get %01111111 11111111 = 32,767

Logged

+1/-0 karm for this message

zStart v1.3.013 9-20-2013

All of my utilities
TI-Connect Help
You can build a statue out of either 1'x1' blocks or 12'x12' blocks. The 1'x1' blocks will take a lot longer, but the final product is worth it.
-Runer112

ben_g

Hey cool I can set a custom title now :)
LV9 Veteran (Next: 1337)
Posts: 1002
Rating: +125/-4
Asm noob

Re: please help me with fixed-point math

« Reply #10 on: May 26, 2011, 02:44:11 pm »

then how do the negative number actually works? I thought the 7th bit on 8 bit numbers was the sign bit, and the 15th one with 16bit numbers, but from what you told me, I think what i thought of negative numbers was totally wrong.

Logged

My projects
- The Lost Survivors (Unreal Engine) ACTIVE [GameCommandoSquad main project]
- Oxo, with single-calc multiplayer and AI (axe) RELEASED (screenshot) (topic)
- An android version of oxo (java) ACTIVE
- A 3D collision detection library (axe) RELEASED! (topic)(screenshot)(more recent screenshot)(screenshot of it being used in a tilemapper)

Spoiler For inactive:

This signature was last updated on 20/04/2015 and may be outdated

thepenguin77

z80 Assembly Master
LV10 31337 u53r (Next: 2000)
Posts: 1594
Rating: +823/-5
The game in my avatar is bit.ly/p0zPWu

Re: please help me with fixed-point math

« Reply #11 on: May 26, 2011, 03:13:10 pm »

Before anything, lets look at unsigned numbers.

All 1 byte numbers:
  0 = 00000000
  1 = 00000001
 57 = 00111001
127 = 01111111
220 = 11011100
253 = 11111101
254 = 11111110
255 = 11111111
256 = 00000000    ;it carried back to 0

So we see that when a number goes past 255 it loops back to 0. Now, if we are going to work with negative numbers, obviously we can't go from -256 to 256 because that is 513 numbers and wouldn't fit into one byte. So instead, we number from -128 to 127.

One byte again:
 127 = 01111111
  15 = 00001111
   2 = 00000010
   1 = 00000001
   0 = 00000000
  -1 = 11111111      ;just like the looping up above, but in reverse
  -2 = 11111110
  -3 = 11111101
  -4 = 11111100
 -57 = 11000111
-126 = 10000010
-127 = 10000001
-128 = 10000000

Which means that while bit 7 and 15 are the sign bits, there is more to a negative number than just the sign bit. You actually have to convert the rest of the number.

Logged

+1/-0 karm for this message

zStart v1.3.013 9-20-2013

All of my utilities
TI-Connect Help
You can build a statue out of either 1'x1' blocks or 12'x12' blocks. The 1'x1' blocks will take a lot longer, but the final product is worth it.
-Runer112

ben_g

Hey cool I can set a custom title now :)
LV9 Veteran (Next: 1337)
Posts: 1002
Rating: +125/-4
Asm noob

Re: please help me with fixed-point math

« Reply #12 on: May 26, 2011, 03:47:34 pm »

will NegHL also make negative numbers positive?

Logged

My projects
- The Lost Survivors (Unreal Engine) ACTIVE [GameCommandoSquad main project]
- Oxo, with single-calc multiplayer and AI (axe) RELEASED (screenshot) (topic)
- An android version of oxo (java) ACTIVE
- A 3D collision detection library (axe) RELEASED! (topic)(screenshot)(more recent screenshot)(screenshot of it being used in a tilemapper)

Spoiler For inactive:

This signature was last updated on 20/04/2015 and may be outdated

thepenguin77

z80 Assembly Master
LV10 31337 u53r (Next: 2000)
Posts: 1594
Rating: +823/-5
The game in my avatar is bit.ly/p0zPWu

Re: please help me with fixed-point math

« Reply #13 on: May 26, 2011, 03:48:41 pm »

Yes. It functions just like the NEG z80 instruction, except it operates on HL not A.

Logged

zStart v1.3.013 9-20-2013

All of my utilities
TI-Connect Help
You can build a statue out of either 1'x1' blocks or 12'x12' blocks. The 1'x1' blocks will take a lot longer, but the final product is worth it.
-Runer112

ben_g

Hey cool I can set a custom title now :)
LV9 Veteran (Next: 1337)
Posts: 1002
Rating: +125/-4
Asm noob

Re: please help me with fixed-point math

« Reply #14 on: May 26, 2011, 04:00:40 pm »

an other attempt on my divide, Will this handle signed numbers correctely?

DivFP:
  ;IN: hl, de
  ;OUT: hl = hl / de
  bit 7, d                          ;start of signed stuff
  jr nz, _DivFP_FirstNeg
  bit 7, h
  jr nz, _DivFP_AnsNeg
  jr z, _DivFP_AnsPos
_DivFP_FirstNeg:
  bit 7, h
  jr nz, _DivFP_AnsPos
_DivFP_AnsNeg:
  ld a, 1
  push af
  jr _DivFP_Cont
_DivFP_AnsPos:
  ld a, 0
  push af
_DivFP_Cont:
  bit 7, h
  jr z, _DivFP_HLPos
  call NegHL
_DivFP_HLPos:
  bit 7, d
  jr z, _DivFP_DEPos
  call NegDE
_DivFP_DEPos                    ;end of signed stuff and start of the unsigned divide
  ld a, h
  ld h, l
  ld l, 0
  call Div24by16
  pop af
  cp 1
  call z, NegHL
  ret

Div24by16:
  push hl ;INPUTS: ahl = dividend de = divisor	;1
  pop ix ;OUTPUTS: ahl = quotient de = divisor	;0
  ld hl,0
  ld b,24
_Div24by16loop:
  add ix,ix
  rla
  adc hl,hl
  jr c,_Div24by16setbit
  or a
  sbc hl,de
  add hl,de
  jr c,_Div24by16skip
_Div24by16setbit:
  or a
  sbc hl,de
  inc ix
_Div24by16skip:
  djnz _Div24by16loop
  push ix			;1
  pop hl			;0
  ret

NegHL:
	xor a
	sub l
	ld l,a
	sbc a,a
	sub h
	ld h,a
	ret

NegBC:
	xor a
	sub c
	ld c,a
	sbc a,a
	sub b
	ld b,a
	ret

NegDE:
	xor a
	sub e
	ld e,a
	sbc a,a
	sub d
	ld d,a
	ret

I hope I've finally got it right

Logged

My projects
- The Lost Survivors (Unreal Engine) ACTIVE [GameCommandoSquad main project]
- Oxo, with single-calc multiplayer and AI (axe) RELEASED (screenshot) (topic)
- An android version of oxo (java) ACTIVE
- A 3D collision detection library (axe) RELEASED! (topic)(screenshot)(more recent screenshot)(screenshot of it being used in a tilemapper)

Spoiler For inactive:

This signature was last updated on 20/04/2015 and may be outdated

Print

Pages: [1] 2 Go Up

« previous next »

Server load over the past 5, 10 and 15 minutes respectively: 0.1640625, 0.25537109375, 0.32666015625

Page created in 0.111 seconds with 63 queries.