pouët.net

Go to bottom

need help with fixed-point mandelbrot on nds

category: general [glöplog]
 
greetings :D

i am working on a real-time mandelbrot zoomer for the nds but i ran into a problem. as imho the best coder's around are in the demoscene,
i thought asking here is the best way to go :)

the floating-point-version runs flawlessly, but after i converted it to fixed-point, it gave me this:

BB Image

Code: a := trunc(-2.2 * (1 shl 8)); s := trunc(-2 * (1 shl 8)); d := trunc((1/52) * (1 shl 8)); f := trunc((1/40) * (1 shl 8)); For sX := 0 to 255 do Begin dx := a + sX * d; For sY := 0 to 191 do Begin Inc(Count); dy := s + sY * f; betrag_sqr := 0; iter := 0; _x := 0; _y := 0; while (betrag_sqr <= 4 * (1 shl 8)) and (iter < 32) do Begin xt := ((_x * _x) shr 8) - ((_y * _y) shr 8) + dx; yt := ((2 * _x * _y) shr 8) + dy; _x := xt; _y := yt; iter := iter + 1; betrag_sqr := ((_x * _x) shr 8) + ((_y * _y) shr 8); End; vram_a[sY * 256 + sX] := rgb15(iter,iter,iter); End; End;


all variables are signed words (word on arm = 32bit)

please ignore that it's pascal and unoptimized, i've already translated it to (still unoptimized *g*) assembler (any ARM-assembler-coders around?),
which gave me the exact same result. i am posting the pascal-code here because it takes less space (and probably is more readable for most of you *g*)

in the asm-code i have already tried dealing with potential 32-bit-overflows, which didn't help. i've searched the web for hours but as i do
not really know what the problem is, i didn't find anything usefull. last idea i've got is a problem with the sign, but i really have no clue.

using a higher/lower shift-value doesn't make any difference here.

any idea what the problem is? or any advices?

thanks in advance.
added on the 2007-09-19 09:21:39 by doc^21o6 doc^21o6
It's not a bug, it's an effect. Anyway looks kinda cooler that way. ;)
added on the 2007-09-19 09:25:26 by waffle waffle
Code:d := trunc((1/52) * (1 shl 8)); f := trunc((1/40) * (1 shl 8));


it seems 1/52 and 1/40 become zero after truncation. Use reals for them.
i guess you've mixed something up here, but thanks for your comment. :)

d = trunc((1/52) * 256) -> d = trunc(~0,01923 * 256)

~0,01923 * 256 = ~4.9228, so after truncating: d = 4 (and f=6)

i probably should use round instead of trunc, but that's not adressing the problem.

btw, using reals kind of collides with the approach of making it fixed-point *g*
added on the 2007-09-19 10:06:42 by doc^21o6 doc^21o6
With the way the image is cut up into chunks I'd say you have a sign problem. And it's most likely that the "shr" operator translates to an unsigned shift. Try dividing by 256 instead of shifting right by 8. If that works, replace your LSR with ASR instructions in the ASM version.
added on the 2007-09-19 10:25:21 by doomdoom doomdoom
YES! That did it!

Thanks a lot, Influence Device! :D

(apparently i have to read the assembler guide again *g*)
added on the 2007-09-19 10:41:56 by doc^21o6 doc^21o6
Dr. Doom to the rescue! \o/
anes your mistake was on thinking Pascal like a highly typed language which's name is C :), actually I'm pretty sure that any Pascal compiler would and obviously must convert any integer division whose result is smaller than 1 to a real type while coding in a "mixed mode" fashion.
added on the 2007-09-19 11:07:34 by decipher decipher
depends on which operator you're using.

int := 1 div 2
float := 1 / 2

using div always gives integers, while using / always gives floating-point-numbers... so you have to take care about mixing yourself.
(hope i understood you correct)

oh and please no C / Pascal-thread ... we all should know that assembler is the only way to go ;)
added on the 2007-09-19 12:05:11 by doc^21o6 doc^21o6
Pascal???
added on the 2007-09-19 13:02:45 by xernobyl xernobyl
Borland Turbo Pascal FTW!
added on the 2007-09-19 13:05:43 by xeron xeron
I welcome you to the "Pascal seriously lacks an arithmetic shift right operator" club ;)
added on the 2007-09-21 12:52:59 by KeyJ KeyJ
doc : "as imho the best coder's around are in the demoscene,"

Hahaha ! Young, bold, and full of bias. I love it ! :))))
added on the 2007-09-21 13:23:46 by TomS4wy3R TomS4wy3R
Although, you'd think the compiler translated constant divs into shifts whenever it could, wouldn't you, minding the signedness of the operands.

So.. NDS is ARM based then? What are the dev tools like?
added on the 2007-09-21 13:37:17 by doomdoom doomdoom
lol KeyJ and Tom. oh and Tom, i am 27 (:p) and as far as i can remember the scene always had the brightest heads in terms of creativity ... not only in the coding-department :)

"Although, you'd think the compiler translated constant divs into shifts whenever it could, wouldn't you, minding the signedness of the operands."

i am sorry, i do not really understand you.
it was my fault, because i actually completely forgot that when shifting to the right i will kill the sign.

yeah, the nds is a dual core risc-machine lacking divide and an fpu *gg*

i'm using the fpc-ide (feels almost like the good old borland pascal ide :D) for editing and there's a port of fpc for the nds, which sometimes seems to have problems with assembler, but maybe that's just me because i'm trying to be armasm-conform (most of the time at least *gg*) ... and the compiler doesn't care about that (see LSL, LSR for example).

devkitpro, which is needed, works 99.9% fine.

fpc produces slow code. ... maybe it's my fault (no it's not *g*), because i'm not writing compiler-friendly code... but i'd rather shoot myself before doing this. that's why i'm just misusing it for assembler and because of libnds... that saves quite some time.

for emulation i am using no$gba, the one great gba/ds-emulator.
the best in my eyes, because it's the only emulator that allows me to run my real-time generated code.

was that what you wanted to know?
added on the 2007-09-21 23:18:54 by doc^21o6 doc^21o6
No problem, Doc. It's always a pleasure to see people that enthusiastic about the Scene. It means that there are good things in this world, and that they are worth fighting for.
added on the 2007-09-22 04:35:09 by TomS4wy3R TomS4wy3R
[qoute]"Although, you'd think the compiler translated constant divs into shifts whenever it could, wouldn't you, minding the signedness of the operands."

i am sorry, i do not really understand you.[/quote]

What I mean is, even if the language doesn't have an arithmetic shift operator, the compiler could still translate a signed-integer division by 256 to an arithmetic shift right by 8.

The dev tools sound nice, though I'd be more C than Pascal. I should look at getting a DS and a dev kit.
added on the 2007-09-22 11:58:29 by doomdoom doomdoom
ah, ok, now i understand you *gg*

the nds has quite a big homebrew-scene, but there don't seem to be that many demos around, so ... go buy one and start coding *gg*
added on the 2007-09-22 12:25:06 by doc^21o6 doc^21o6
Quote:
even if the language doesn't have an arithmetic shift operator, the compiler could still translate a signed-integer division by 256 to an arithmetic shift right by 8

If the compiler does that, it deserves to be stabbed, shot and buried, though not necessarily in that order. x/256 and x>>8 is *not* the same thing for signed integers, because integer division rounds towards zero while shifting rounds towards negative infinity.
added on the 2007-09-25 11:50:04 by KeyJ KeyJ
Quote:

If the compiler does that, it deserves to be stabbed, shot and buried, though not necessarily in that order. x/256 and x>>8 is *not* the same thing for signed integers, because integer division rounds towards zero while shifting rounds towards negative infinity.


Actually, a lot of compilers, MSVC included, translates integer division by a power of two constant into just that, an arithmetic shift right, but also adds a couple of instructions to fix up the rounding. Still faster than a real divide, but gets you the result you want.
added on the 2007-09-25 16:07:10 by ector ector
ector: That's right, and this kind of optimization is fully appreciated. But more often than not you actually *want* the rounding behaviour of the shift operation. In this case, you absolutely need a shift operator, because dividing by 2**n just doesn't do the trick. That was my point.
added on the 2007-09-25 19:23:17 by KeyJ KeyJ
Those are good points :)
added on the 2007-09-25 21:32:20 by doomdoom doomdoom

login

Go to top