Author Topic: Fixed point division?  (Read 11727 times)

0 Members and 1 Guest are viewing this topic.

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Fixed point division?
« on: June 16, 2011, 02:43:01 pm »
For the contest, I am doing this thing that involves a raycasting. I would just use bwang's engine, but I'm guessing it would hurt my originality score, and it is kind of slow with all the features he added and the fact it uses floating point math. So, I'm writing my own, with fixed point math and less features, but I can't wrap my head around fixed point division. Can someone explain it to me? I'm using a 16.16 format, if it matters.

Offline calc84maniac

  • eZ80 Guru
  • Coder Of Tomorrow
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2912
  • Rating: +471/-17
    • View Profile
    • TI-Boy CE
Re: Fixed point division?
« Reply #1 on: June 16, 2011, 03:10:08 pm »
You're using a 16.16 format? That seems a bit overkill, and it even makes adding/subtracting hard, right?

Edit: OHWAIT this is for the Nspire contest. durrrr

Edit2:
I think something like this is how it's done:
int quotient = ((long long)dividend << 16)/divisor;
« Last Edit: June 16, 2011, 03:16:09 pm by calc84maniac »
"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: Fixed point division?
« Reply #2 on: June 16, 2011, 03:21:11 pm »
Thanks!
Also, just want to make sure, am I doing multiplication right?
product = (a >> 8) * (b >> 8)
product = (a >> 8 ) * (b >> 8 )
« Last Edit: June 16, 2011, 03:24:10 pm by fb39ca4 »

Offline calc84maniac

  • eZ80 Guru
  • Coder Of Tomorrow
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2912
  • Rating: +471/-17
    • View Profile
    • TI-Boy CE
Re: Fixed point division?
« Reply #3 on: June 16, 2011, 03:25:08 pm »
Thanks!
Also, just want to make sure, am I doing multiplication right?
product = (a >> 8) * (b >> 8)
If you want a fully accurate answer, I think you'd need ((long long)a * b) >> 16

Hmm, maybe I should write some ARM ASM routines for fixed-point multiplication/division. Doing it normally through GCC is going to be a bit inefficient.

Edit:
Just to confirm, are you using signed values?
« Last Edit: June 16, 2011, 03:29:30 pm by calc84maniac »
"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: Fixed point division?
« Reply #4 on: June 16, 2011, 03:46:40 pm »
But the way I did it would prevent overflows, because I am only using 32 bit integers the whole time. In my case, not getting the integer part right would be worse than getting a tiny part of the fractional part wrong.
Yes, I'm using signed numbers. Will that introduce problems?
Also, am I understanding the division correctly? a / b in fixed point is [integer part of a]/b?
Can you use 64 bit numbers on the Nspire?

Hey, it's my 888th post!
« Last Edit: June 16, 2011, 03:59:39 pm by fb39ca4 »

Offline calc84maniac

  • eZ80 Guru
  • Coder Of Tomorrow
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2912
  • Rating: +471/-17
    • View Profile
    • TI-Boy CE
Re: Fixed point division?
« Reply #5 on: June 16, 2011, 03:53:47 pm »
But the way I did it would prevent overflows, because I am only using 32 bit integers the whole time.
Yes, I'm using signed numbers. Will that introduce problems?
Also, am I understanding the division correctly? a / b in fixed point is [integer part of a]/b?
You can have overflow when multiplying 32-bit integers, if the absolute value of the result is more than 2^31. If you want, I could implement saturation in my routines (so anything outside of the range will be turned into the maximum or minimum value).

And the division is (a * 2^16)/b (this is to nullify the factor of 2^16 present in b)
"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: Fixed point division?
« Reply #6 on: June 16, 2011, 04:31:26 pm »
Apparently ARM7 does not natively support long long integers. So that means I would get odd results if I tried division with any number with an absolute value of over 1.
Would (a <<  8 ) / (b >>  8 ) work? I would still get an overflow if I used anything over 65536 in fixed point, but I don't think I will get to numbers that high.
Also, is there a tag to disable smileys?
« Last Edit: June 16, 2011, 04:31:53 pm by fb39ca4 »

Offline calc84maniac

  • eZ80 Guru
  • Coder Of Tomorrow
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2912
  • Rating: +471/-17
    • View Profile
    • TI-Boy CE
Re: Fixed point division?
« Reply #7 on: June 16, 2011, 05:08:54 pm »
Apparently ARM7 does not natively support long long integers. So that means I would get odd results if I tried division with any number with an absolute value of over 1.
Would (a <<  8 ) / (b >>  8 ) work? I would still get an overflow if I used anything over 65536 in fixed point, but I don't think I will get to numbers that high.
Also, is there a tag to disable smileys?
No ARM processor natively supports 64-bit, but GCC should be able to generate code anyway.
A big problem with (a << 8) / (b >> 8) is that the top 8 bits of a are lost before the division. This means that numbers greater than 256 wouldn't work.

By the way, I've finished with a fixed-point multiplication routine now and I'm working on division. You should be able to put this in a .S file and include it in your makefile, and you can use it if you define the function prototype in your C code.
Code: [Select]
@ int fixed_mul(int, int);
.global fixed_mul
fixed_mul:
@ Multiply 32x32->64 and shift right by 16
smull r0,r2,r1,r0
mov r0,r0,lsr #16
orr r0,r0,r2,lsl #16
@ Overflow check start
teq r2,r0,asr #16
movne r0,#0x7FFFFFFF
eorne r0,r0,r2,asr #31
@ Overflow check end
bx lr

Edit: Here's the fixed-point division routine (note: neither of these routines have been tested yet)
Code: [Select]
@ int fixed_div(int, int);
.global fixed_div
fixed_div:
@ r2 = abs(r0)
eors r2,r0,r0,asr #32
adc r2,r2,#0
@ r3 = abs(r1)
eors r3,r1,r1,asr #32
adc r3,r3,#0
@ Get sign of result
eor r1,r1,r0
@ Initialize result
mov r0,#0x7FFFFFFF
@ Check for overflow
cmp r3,r2,lsr #15
bls fixed_div_end

.irp shift,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0
cmp r3,r2,lsr #\shift
subls r2,r2,r3,lsl #\shift
bichi r0,r0,#0x10000 << \shift
.endr
.irp shift,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0
rsbs r2,r3,r2,lsl #1
addlo r2,r2,r3
biclo r0,r0,#1 << \shift
.endr

fixed_div_end:
@ Adjust sign
eors r0,r0,r1,asr #32
adc r0,r0,#0
bx lr

Edit2: It's looking likely that the division routine doesn't work :(

Edit3: Replaced the division routine with one that might work (at least, the equivalent C code seems to work)
« Last Edit: June 16, 2011, 09:36:41 pm by calc84maniac »
"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: Fixed point division?
« Reply #8 on: June 17, 2011, 11:41:38 am »
For my purposes, it will be fine, as I don't expect to have maps greater than 64 or so blocks, and 1 unit in my engine is a block.

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: Fixed point division?
« Reply #9 on: June 19, 2011, 02:27:27 pm »
I was getting major errors so I replaced my multiply and divides with the ones in C you mentioned above, using long longs, and now I am getting errors when I compile:
Code: [Select]
$ make
nspire-gcc -Os -Wall -W -c main.c
main.c: In function 'main':
main.c:52:7: warning: unused variable 'oldtime'
main.c:51:7: warning: unused variable 'time'
main.c:46:8: warning: unused variable 'timer'
nspire-gcc -Os -Wall -W -c utils.c
utils.c: In function 'filesize':
utils.c:129:3: warning: passing argument 2 of 'stat' from incompatible pointer type
c:/ndless-v2.0/sdk/include/os.h:288:1: note: expected 'struct stat *' but argument is of type 'char *'
nspire-gcc -Os -Wall -W -c graphics.c
nspire-gcc -Os -Wall -W -c math.c
nspire-ld  main.o utils.o graphics.o math.o -o raycaster.elf
c:/program files/yagarto/bin/../lib/gcc/arm-none-eabi/4.5.1\libgcc.a(unwind-arm.o): In function `get_eit_entry':
C:\msys\1.0\home\yagarto\gcc-build\arm-none-eabi\libgcc/../../../gcc-4.5.1/libgcc/../gcc/config/arm/unwind-arm.c:614: undefined reference to `__exidx_start'
C:\msys\1.0\home\yagarto\gcc-build\arm-none-eabi\libgcc/../../../gcc-4.5.1/libgcc/../gcc/config/arm/unwind-arm.c:614: undefined reference to `__exidx_end'
c:/program files/yagarto/bin/../lib/gcc/arm-none-eabi/4.5.1/../../../../arm-none-eabi/lib\libc.a(lib_a-abort.o): In function `abort':
C:\msys\1.0\home\yagarto\newlib-build\arm-none-eabi\newlib\libc\stdlib/../../../../../newlib-1.18.0/newlib/libc/stdlib/abort.c:63: undefined reference to `_exit'
c:/program files/yagarto/bin/../lib/gcc/arm-none-eabi/4.5.1/../../../../arm-none-eabi/lib\libc.a(lib_a-signalr.o): In function `_kill_r':
C:\msys\1.0\home\yagarto\newlib-build\arm-none-eabi\newlib\libc\reent/../../../../../newlib-1.18.0/newlib/libc/reent/signalr.c:61: undefined reference to `_kill'
c:/program files/yagarto/bin/../lib/gcc/arm-none-eabi/4.5.1/../../../../arm-none-eabi/lib\libc.a(lib_a-signalr.o): In function `_getpid_r':
C:\msys\1.0\home\yagarto\newlib-build\arm-none-eabi\newlib\libc\reent/../../../../../newlib-1.18.0/newlib/libc/reent/signalr.c:96: undefined reference to `_getpid'
collect2: ld returned 1 exit status
make: *** [raycaster.tns] Error 1
« Last Edit: June 19, 2011, 02:27:55 pm by fb39ca4 »

Offline Lionel Debroux

  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2135
  • Rating: +290/-45
    • View Profile
    • TI-Chess Team
Re: Fixed point division?
« Reply #10 on: June 19, 2011, 03:08:16 pm »
The kill and getpid POSIX calls aren't referenced by your program, but by stuff internal to newlib, and stuff which shouldn't be linked with your program, at that...
Try the -nostdlib flag. A number of open-coded operations (e.g. 32-bit division) won't be accessible, but it may remove references to kill, getpid and friends.

And "utils.c:129:3: warning: passing argument 2 of 'stat' from incompatible pointer type + c:/ndless-v2.0/sdk/include/os.h:288:1: note: expected 'struct stat *' but argument is of type 'char *'" is a very important warning. Fix it, so that the incorrect generated code does not bite you at runtime.
Member of the TI-Chess Team.
Co-maintainer of GCC4TI (GCC4TI online documentation), TILP and TIEmu.
Co-admin of TI-Planet.

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: Fixed point division?
« Reply #11 on: June 19, 2011, 03:49:14 pm »
Okay, I just removed the function from utils.c that gave the warning since I'm not using it anyways. I also tried using -nostdlib, and the compiler output looks normal, but I don't get a tns document. Also, not having 32 bit division will be an issue for me if I get -nostdlib working.

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: Fixed point division?
« Reply #12 on: June 19, 2011, 08:36:18 pm »
The error messages disappear when I don't use long long, so I set about writing a division routine that does not use long long.
Can someone confirm this works?
Code: [Select]
inline long div(long a, long b) {
  long a1;
  a1 = a >> 16;
  a = (a << 16) / b;
  a1 = (a1 << 16) / b;
  return (a1 << 16) + a;
}
« Last Edit: June 19, 2011, 08:37:01 pm by fb39ca4 »

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: Fixed point division?
« Reply #13 on: June 20, 2011, 03:44:41 pm »
I have a multiplication routine which almost works. Basically, I isolate the upper and lower halves of a and b each to the bottom half of a new variable, use the FOIL method and add them together.
Code: [Select]
inline long mul(long a, long b) {
  long a1 = a >> 16;
  long a2 = a & 0x0000FFFF;
  long b1 = b >> 16;
  long b2 = b & 0x0000FFFF;
  return ((a1 * b1) << 16) + (a1 * b2) + (a2 * b1) + ((a2 + b2) << 16);
}
I tried to multiply 0x00028000 and 0x0002000 (2 * 2.5), but I got 0x80050000, it seems that the sign bit gets messed up. What am I doing wrong?

Offline calc84maniac

  • eZ80 Guru
  • Coder Of Tomorrow
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2912
  • Rating: +471/-17
    • View Profile
    • TI-Boy CE
Re: Fixed point division?
« Reply #14 on: June 20, 2011, 04:59:24 pm »
I think your ((a2 + b2) << 16) needs to be ((a2*b2) >> 16). Actually, I think it might be a good idea to specify your variables there as unsigned short and signed short, like so (otherwise the ((a2*b2)>>16) might turn out badly):
Code: [Select]
inline long mul(long a, long b) {
  signed short a1 = a >> 16;
  unsigned short a2 = a;
  signed short b1 = b >> 16;
  unsigned short b2 = b;
  return ((a1 * b1) << 16) + (a1 * b2) + (a2 * b1) + ((a2 * b2) >> 16);
}
"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman