I just released a bit of e-reader information too, including a dotcode
printing tool (some ppl already have it), more to follow soon...

http://users.skynet.be/firefly/gba/e-reader/

-----Original Message-----
From: Damien Good [mailto:d_good@...]
Sent: woensdag 31 december 2003 3:42
To: gbadev@yahoogroups.com
Subject: Re: [gbadev] Re: e-Reader dissection

http://www.alpha-ii.com/caitsith2/ereader/dot-code%20block.jpg - explanation
on how the raw data is stored in the dotcode blocks in the strip.

Now, the only thing that is really stopping us from
developing our own dotcodes, is the fact that we do not know how to
encode/decode the nintendo specific reed-solomon codes.

essentially, it goes like this.

Binary data + reed-solomon codes = Raw data. (unsolved)
Raw data + 8/10 Modulation = Dotcode dots. (solved)

It would be helpful to know where the e-reader functions are, in the rom,
and what each of them does.  maybe we can reverse engineer the reed-solomon
encoding/decoding out of one of the functions.

Sgstair was telling me that they have downloaded the code and are looking at
it.  He can tell you how to access that data..

----- Original Message -----
From: "Damien Good" <d_good@...>
To: <gbadev@yahoogroups.com>
Sent: Tuesday, December 30, 2003 6:41 PM
Subject: Re: [gbadev] Re: e-Reader dissection


> http://www.alpha-ii.com/caitsith2/ereader/dot-code%20block.jpg -
explanation
> on how the raw data is stored in the dotcode blocks in the strip.
>
> Now, the only thing that is really stopping us from
> developing our own dotcodes, is the fact that we do not know how to
> encode/decode the nintendo specific reed-solomon codes.
>
> essentially, it goes like this.
>
> Binary data + reed-solomon codes = Raw data. (unsolved)
> Raw data + 8/10 Modulation = Dotcode dots. (solved)
>
> It would be helpful to know where the e-reader functions are, in the rom,
> and what each of them does.  maybe we can reverse engineer the
reed-solomon
> encoding/decoding out of one of the functions.

--- In gbadev@yahoogroups.com, "ronald_chenu" <ronald_chenu@y...>
wrote:
>
> Caching to the EXTRAM (or VRAM itself by double buffering) will have
> the following (+)positive and (-)negative  consequences:

(paraphrasing here)

> (+) Caching in EWRAM allows use of draw time for decompression.
Correct.  EWRAM to VRAM transfers run at 4 cycles per 2 bytes,
filling the entire 32 KB sprite cel VRAM within about 66,000
cycles.  Vblank is 83,776 cycles long.

> (-) Caching uses EWRAM.
Correct.

> (-) Caching uses time to move data into EWRAM.
Correct.

> And the most important of all:
> (-)Consumes greater cpu time.

Not necessarily.  If you are transferring the same images over
and over to VRAM, such as 12 frames of a walk loop, you save
the time of repeated decompression.  You can also decompress
ahead of the animation when you know you have a lot of CPU
time to spare in this frame's draw period.

> This will work remarkably well if you have spare time outside
> vblank

In my experience, most 2D programs for GBA have much more
spare time outside vblank than they know what to do with.
Still, efficient coding will drain the battery less.

--
Damian

http://www.alpha-ii.com/caitsith2/ereader/dot-code%20block.jpg - explanation
on how the raw data is stored in the dotcode blocks in the strip.

Now, the only thing that is really stopping us from
developing our own dotcodes, is the fact that we do not know how to
encode/decode the nintendo specific reed-solomon codes.

essentially, it goes like this.

Binary data + reed-solomon codes = Raw data. (unsolved)
Raw data + 8/10 Modulation = Dotcode dots. (solved)

It would be helpful to know where the e-reader functions are, in the rom,
and what each of them does.  maybe we can reverse engineer the reed-solomon
encoding/decoding out of one of the functions.

> Ever tried caching decompressed cels in EWRAM?
>
> --
> Damian
The following are my assumptions, please feel free to correct them.

Caching to the EXTRAM (or VRAM itself by double buffering) will have
the following (+)positive and (-)negative  consequences:
(+)If you are streaming compressed frames of a sprite, in addition of
using vblank time for doing decompression and transfer, caching will
also allow you to use time outside vblank for this purpose and thus
increasing the amount of data decompressed in each frame.
(-)Consumes extra EXTRAM/VRAM. (not really important since usually
there is quite a lot of free EXTRAM in most applications)
(-)Cached data has to be re-transfered to VRAM during vblank (since
the data is already decompressed a quick DMA should lessen the blow)

And the most important of all:
(-)Consumes greater cpu time.

Which brings me to the conclusion that caching data to make up for
poor transfer speeds (due to compressed data) will give you more time
to complete your transfers (because you can use out of vblank
scanlines) although at the cost of greater cpu usage, since you will
be doing data transfers inside AND outside the vblank.

This will work remarkably well if you have spare time outside vblank,
because inside vblank, all you need to do is to quickly DMA from
EXTRAM to VRAM.

But if this is not the case, the only way (I think) to achieve higher
transfer speeds would be using a simpler compression algorithm (like
RLE), or even...., not compressing data.. >_< .

Thanks for answering.

Ronald

--- In gbadev@yahoogroups.com, "ronald_chenu" <ronald_chenu@y...> wrote:
> >LZ77 compressed sprites were used in Battle Bots game.
> >They were depacked in real time.
> Thats exactly what I'm trying to do, but 300 KB per sec
> (5 per frame at 60fps) it not going to work for me :(

Ever tried caching decompressed cels in EWRAM?

--
Damian

Merry Christmas to all!

>>RCA> Has anyone made tests on the speed of the LZ77
>>RCA>Bios decompression funcions?
>>about 300-500 kilobytes per second

I see, but since you are actually making a transfer of less data
(because of the compression) that would become 360-600 KB per second
assuming the compressed data is 80% the size of the uncompressed data,
right?

Even considering that, It seems that the overhead of decompressing
lz77 its quite hard on the transmission speed.

What about RLE?  Has anyone tried it?
It should be a little faster than lz77(because the algorithm is less
complex)

>>RCA> How do they compare with CpuSet and FastCpuSet?
>>RCA>and DMA Transfer?
>>CpuSet, CpuFastSet and DMA transfer is much faster
>>(up to 30-40times)
Is that number relative to  DMA or the Bios functions?
Because I think there is quite a difference of speed between them.

>LZ77 compressed sprites were used in Battle Bots game. They were
>depacked in real time.
Thats exactly what I'm trying to do, but 300 KB per sec (5 per frame
at 60fps) it not going to work for me :(

Thanks for answering and saving me from long testing hours : )

Ronald

Hello Ronald,

Wednesday, December 24, 2003, 12:50:04 AM, you wrote:

RCA> Has anyone made tests on the speed of the LZ77 Bios
RCA> decompression funcions?

about 300-500 kilobytes per second

RCA> How do they compare with CpuSet and FastCpuSet? and
RCA> DMA Transfer?

  CpuSet, CpuFastSet and DMA transfer is much faster (up to 30-40
times)

RCA> All of them copy data from source to destination
RCA> (albeit with compression read data is normally smaller
RCA> than written data) so a relative comparison would be
RCA> possible and would be very useful in deciding when to
RCA> use compression.

  LZ77 compressed sprites were used in Battle Bots game. They were
depacked in real time.

WinAmp is Sleeping...
-- [ZX][GBA][Scene][Anime][Ot.A.Ma.][B.A.K.A. S.T.][Powered by Jenechka]
Best regards,
  Vivid / Brainwave Team                    mailto:vivid@...

Hi GBAlist!

Has anyone made tests on the speed of the LZ77 Bios
decompression funcions?

How do they compare with CpuSet and FastCpuSet? and
DMA Transfer?

All of them copy data from source to destination
(albeit with compression read data is normally smaller
than written data) so a relative comparison would be
possible and would be very useful in deciding when to
use compression.

Thanks in advance

Ronald

Well, it seems Harbour's Unnofficial Guide officially went awry. I just
realized he is providing the book in PDF format through his web page
(http://www.jharbour.com/gameboy/) and selling the source code via PayPal.

   I can only guess what were their licensing troubles with Nintendo...

   Cheer up!


--               /"I have always found that Angels have the vanity to
PabloBleyerKocik/ speak of themselves as the only wise; this they do
   pbleyer       / with a confident insolence sprouting from systematic
    @embedded.cl/ reasoning."-The Marriage of Heaven and Hell, W. Blake

I WOULD NOT recommend HONG KONG TOYS http://www.ps2modchip.com/ ...
They get the money and they don't send the hardware...unluckily
I had a bad experience this time, so better you guys don't make
the same mistake...:-(
They seemed attractive, good price and good email response time...
but once paid...nothing else....well for the moment, they
should not be replying people ...they have a lot of emails
to read :-)

cheers,
marc

PS: I am still looking for another good shop in Hong Kong so any
feedback appreciated.

--- In gbadev@yahoogroups.com, "Janwillem Naesens" <sisghidir@h...>
wrote:
> Now maybe someone over here, having ever made a flash cart
> of his own, has know similar problems? Or maybe anyone could
> pass me a detailed timing report on the protocols?

You mean beyond what's here?
http://www.ziegler.desaign.de/GBA/gba.htm

> Or if anyone has been able to decode the logo sequence, or
> maybe just the order in which the gba reads it...

The 156-byte "Magic Cookie Data" from 0x08000004 to 0x0800009f
is a Huffman-compressed representation of the Nintendo logo.
You can create a proper header, including the MCD, by using
any of the header tools available at gbadev.org.  If you
already have a proper header, then you have protocol problems.

> PS: monday we're going to try connect using the link port and a
parallel cable to the PC. But I don't actually know if it is possible
to read from the cartridge through that port.

It is possible. The MBV2 cable can dump carts:

mb -1 rom.gba -w 300

(that's a dash one not a dash L)

--
Damian

Hi there,

Here at the univ we're having a little project on the gba: we're trying to
connect one to an FPGA. To use the FPGA as a 'living cartridge'. (kinda like the
Xport at www.charmedlabs.com). Now to start, we just use the FPGA to do a little
interface and we use genuine gba ROM's that we upload in a RAM-chip. Problem is
that all we get out of the gba is a scrambled nintendo logo. We put analysers on
all signals, logged the incoming adresses and outgoing data, tried 100,000
different ROM's, but nothing helps.
Now maybe someone over here, having ever made a flash cart of his own, has know
similar problems? Or maybe anyone could pass me a detailed timing report on the
protocols? Or if anyone has been able to decode the logo sequence, or maybe just
the order in which the gba reads it...

unbelievebly gratefull,

Sis

PS: monday we're going to try connect using the link port and a parallel cable
to the PC. But I don't actually know if it is possible to read from the
cartridge through that port. Maybe anyone has info on that?

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Friday 12 December 2003 04:02 am, dagamer34 wrote:
> Actually, In your makefile, instead of gcc .....(options) type
> g++ .... (options). The libraries should (don't quote me on it
> though) automatically be linked in with the rest of your project. If
> all else fails, someone else should know.
I'm pretty sure gcc is the same as g++ when it's called with a .cpp
extention...
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (GNU/Linux)

iD8DBQE/2UURZl/BHdU+lYMRAuPXAJ0Y863aNHPF9TjSkhx/dX3+8VMtIQCcDab2
txbezg5bhxRQHkD+VkfEYdM=
=CjIR
-----END PGP SIGNATURE-----

Actually, In your makefile, instead of gcc .....(options) type
g++ .... (options). The libraries should (don't quote me on it
though) automatically be linked in with the rest of your project. If
all else fails, someone else should know.

--- In gbadev@yahoogroups.com, <gbadev@r...> wrote:
> Hi,
>
>
>
> I've been trying to get a C++ project to compile using Devkit
Advance
> (release 5 beta 3) ideally along with Jeff's Crt0 and LnkScript
(crtls
> v1.28).  Which libraries do I need to link for C++ compilation?
I'd be very
> grateful if someone would post a sample makefile that would work
for this
> (even if it compiles/links just a single cpp file).
>
>
>
> Thanks in advance.

Sure, gcc and most other compilers use software floating point
operations if you dont have the hardware (well you have to tell the
compiler which way to do it).

Take some code like this:

float a,b,c;

void myfun ( void )
{
	 a=b+c;
}

And compile to asm and see what it produces

For example the gcc I use produced code like this

	 ldr r0, [r3, #0] @ float
	 ldr r1, [r2, #0] @ float
	 bl __addsf3
	 mov r3, r0
	 str r3, [r4, #0] @ float

Which is a soft fpu,

add -mhard-float to the command line and you get hardware fpu
instructions:

	 ldfs f1, [r3, #0]
	 ldfs f0, [r2, #0]
	 adfs f0, f1, f0
	 stfs f0, [r1, #0]


You dont want that, if you see f registers and adfs or adfd it is
building for a hard fpu...

And it runs as fast as it runs...

David








On Thu, 2003-12-11 at 08:13, Martijn Reuvers wrote:
> Hi all,
>
> Thanks for your comments, but please assume that I DO want to use floating
> point operations and not fixed point. There are only two operations that I'm
> interested in, addition and integer conversion. Is it possible at all to get
> these simple (to me) instructions fast on the AGB?
>
> Regards,
>
> Martijn
>
>
> ----- Original Message -----
> From: "Tomas Hallenberg" <tomha219@...>
> To: <gbadev@yahoogroups.com>
> Sent: Thursday 11 December 2003 15:30
> Subject: Re: [gbadev] Floating point questions
>
>
> > I don't see the reason for using any floating point arithmetics if
> > that's all you want to do. To begin with you'll only have integer
> > results unless you also have floating point constants, but then you
> > could do it with fixed point instead with good precision.
> >
> > Martijn Reuvers wrote:
> > > Hi,
> > >
> > > I want to do two floating point operations: addition/substraction and
> > > integer conversion. Is there any info on how fast these two operations
> are
> > > on the AGB since it hasn't any FP hardware? How many instructions,
> cycles?
> > > If it's really slow, does anyone know a fast trick to do these two
> > > operations?
> > >
> > > Regards,
> > >
> > > Martijn Reuvers
> >
> > --
> > http://dreamcache.mine.nu
> >
> >
> >
> >
> >
> >
> > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
> >
> >
>
>
>
>
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

Hi all,

Thanks for your comments, but please assume that I DO want to use floating
point operations and not fixed point. There are only two operations that I'm
interested in, addition and integer conversion. Is it possible at all to get
these simple (to me) instructions fast on the AGB?

Regards,

Martijn


----- Original Message -----
From: "Tomas Hallenberg" <tomha219@...>
To: <gbadev@yahoogroups.com>
Sent: Thursday 11 December 2003 15:30
Subject: Re: [gbadev] Floating point questions


> I don't see the reason for using any floating point arithmetics if
> that's all you want to do. To begin with you'll only have integer
> results unless you also have floating point constants, but then you
> could do it with fixed point instead with good precision.
>
> Martijn Reuvers wrote:
> > Hi,
> >
> > I want to do two floating point operations: addition/substraction and
> > integer conversion. Is there any info on how fast these two operations
are
> > on the AGB since it hasn't any FP hardware? How many instructions,
cycles?
> > If it's really slow, does anyone know a fast trick to do these two
> > operations?
> >
> > Regards,
> >
> > Martijn Reuvers
>
> --
> http://dreamcache.mine.nu
>
>
>
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

Hi,



I've been trying to get a C++ project to compile using Devkit Advance
(release 5 beta 3) ideally along with Jeff's Crt0 and LnkScript (crtls
v1.28).  Which libraries do I need to link for C++ compilation?  I'd be very
grateful if someone would post a sample makefile that would work for this
(even if it compiles/links just a single cpp file).



Thanks in advance.

I don't see the reason for using any floating point arithmetics if
that's all you want to do. To begin with you'll only have integer
results unless you also have floating point constants, but then you
could do it with fixed point instead with good precision.

Martijn Reuvers wrote:
> Hi,
>
> I want to do two floating point operations: addition/substraction and
> integer conversion. Is there any info on how fast these two operations are
> on the AGB since it hasn't any FP hardware? How many instructions, cycles?
> If it's really slow, does anyone know a fast trick to do these two
> operations?
>
> Regards,
>
> Martijn Reuvers

--
http://dreamcache.mine.nu

Hi,

I want to do two floating point operations: addition/substraction and
integer conversion. Is there any info on how fast these two operations are
on the AGB since it hasn't any FP hardware? How many instructions, cycles?
If it's really slow, does anyone know a fast trick to do these two
operations?

Regards,

Martijn Reuvers

i've used this for several commercial gba games.  it's fast, simple, and
time-tested.  mersenne twister-strength algorithms are generally not needed
for game-specific needs.  no need to do the mode switch to ARM for so few
lines of assembly:

// C++ code
enum
{
    RAND_SLOPE = 0x41c64e6d,
    RAND_INTERCEPT = 0x3039,
    RAND_SEED = 1,
};

static unsigned int sRandomPlant = RAND_SEED;

int rand()
{
    sRandomPlant = (sRandomPlant * RAND_SLOPE) + RAND_INTERCEPT;
    return static_cast<int>(sRandomPlant >> 17); // RAND_MAX = 0x7fff
}

// THUMB asm
RAND_SEED  = 1
RAND_SLOPE  = 0x3039
RAND_INTERCEPT = 0x41c64e6d

  .data

randPlant:
  .word RAND_SEED

  .text
  .thumb

  .thumb_func
rand:
  ldr r3, =randPlant
  ldr r0, [r3]
  ldr r1, intercept
  ldr r2, slope
  mul r0, r0, r2
  add r0, r0, r1
  str r0, [r3]
  lsr r0, #17
  bx  lr

regards,
matt.

----- Original Message -----
From: "Graeme Cowie" <mcgeezer@...>
To: <gbadev@yahoogroups.com>
Sent: Tuesday, December 09, 2003 3:02 PM
Subject: [gbadev] Random number function


Hi gbadev forum,

Rather than re-invent the wheel trying to write an ARM random number
gernerator function, i thought i'd ask if anyone has done this before or if
there is an easy fast way to achieve random numbers.

I'm thinking of doing a GBA conversion of the classic Atari 8bit version of
River Raid, which generates terrain and enemies randomly.

Cheers,

McGeezer

You are right, what an idiot I am ('specially considering that I did
that very thing two years ago when emulating bios for cowbite).  I
need to get more sleep.  Kids, make sure you finish school *before*
going to work full time, rather than concurrently.

Anyway, the 2.30 square root is around 50% faster (according to my
ghetto colored-scanlines measuring method).  I did not test this
rigoruosly, however.

Also, I actually contacted the original author of that code, and he
wrote back saying that rather than shifting right by 10 at the end, I
can simply replace the "count = 30;" with "count = 20;" and I'll get
the same results for less iterations.  Looking at Demian's
explanation below, I'd guess the '20' comes by doing 30 - (30-n)/2,
where n is my 10 binary places.

Tom


--- In gbadev@yahoogroups.com, "Graham Wall" <graham@t...> wrote:
> Do bear in mind that if you test the speed of the BIOS functions on
an
> emulator the result will not necessarily be indicative of what
happens on
> real hardware. The emulators generally just do a sqrt in native
80x86 code
> and return the result.
>
> Graham
>
> -----Original Message-----
> From: Thomas [mailto:sorcererxiii@y...]
> Sent: 09 December 2003 16:23
> To: gbadev@yahoogroups.com
> Subject: [gbadev] Re: Fixed Point Square Root
>
>
> Ok, testing has revealed that the bios function is a good 10 times
> faster than the 2.30 function (I didn't measure it precisely - all I
> need to know is that it's faster).  To get more precision, I
multiply
> the input by 4096 then divide the result by sqrt(4096).
>
> (Sqrt(fixedval << 12) << 5) >> 6
>
> Of course, this limits us to a max input of 512.0, which is
> sufficient for what it's being used.
>
> Tom
>
>
> --- In gbadev@yahoogroups.com, "Thomas" <sorcererxiii@y...> wrote:
> > Thanks, I'll try that out . . . for some reason my brain is not
> > working on this issue (years of only having to press the square
> root
> > key on a calculator?).  I also figured out that I can use the bios
> > square root (I think) by realizing that
> >
> > sqrt(n * 1024) = sqrt(n)*sqrt(1024) = sqrt(n) << 5.
> >
> > I'll need to compare to see which method is faster/more accurate.
> >
> > Tom
> >
> >
> > --- In gbadev@yahoogroups.com, "Damian Yerrick" <d_yerrick@h...>
> > wrote:
> > > --- In gbadev@yahoogroups.com, "Thomas" <sorcererxiii@y...>
wrote:
> > > > I'd like a general algorithm in C or psuedocode that could be
> > > > used for different fraction sizes just be changing a #define
> > > > value.  I've searched and found some that worked for specific
> > > > cases (like one that was 2.30)
> > >
> > > For reference, here's an example of a 2.30 square root function:
> > > http://www.worldserver.com/turk/opensource/FractSqrt.c.txt
> > >
> > > > but I could figure out how to adapt it for 22.10.
> > >
> > > The given code gives sqrt(1<<30) == 1<<30.  You want
> > > sqrt(1<<10) == 1<<10 and sqrt(1<<30) == 1<<20.  So use the
> > > 2.30 code and just shift the result right by 10 binary places.
> > > In general, if you have n fractional places (in your case 10),
> > > where n is odd and 0 <= n <= 30, then shift right by (30-n)/2
> > > after calling the 2.30 routine.
> > >
> > > Division is rather slow on ARM; don't use the division based
> > > Newton's method code that somebody else just posted.
> > >
> > > --
> > > Damian
>
>
>
> Yahoo! Groups Sponsor
> ADVERTISEMENT
>
>
>
>
> Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.

Man, I lost so much of my childhood to that game :)

There was a thread on this mailing list ages ago about this. Try
searching the archives for "mersenne twister", as i know that was mentioned.


alex:)


Graeme Cowie wrote:
> Hi gbadev forum,
>
> Rather than re-invent the wheel trying to write an ARM random number
> gernerator function, i thought i'd ask if anyone has done this before or
> if there is an easy fast way to achieve random numbers.
>
> I'm thinking of doing a GBA conversion of the classic Atari 8bit version
> of River Raid, which generates terrain and enemies randomly.
>
> Cheers,
>
> McGeezer
>
> *Yahoo! Groups Sponsor*
> ADVERTISEMENT
>
<http://rd.yahoo.com/SIG=12ckv5dmt/M=267637.4116730.5333196.1261774/D=egroupweb/\
S=1705055196:HM/EXP=1071087444/A=1853618/R=0/*http://www.netflix.com/Default?mqs\
o=60178338&partid=4116730>
>
>
> Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service
> <http://docs.yahoo.com/info/terms/>.



________________________________________________________________________
This email has been scanned for all viruses by the MessageLabs Email
Security System. For more information on a proactive email security
service working around the clock, around the globe, visit
http://www.messagelabs.com
________________________________________________________________________

Take a look at the Mersenne Twister, or the Mitchell Moore algorithm. Both of
them are fast, good and don't require too much memory.

Guido

   ----- Original Message -----
   From: Graeme Cowie
   To: gbadev@yahoogroups.com
   Sent: Tuesday, December 09, 2003 12:02 PM
   Subject: [gbadev] Random number function


   Hi gbadev forum,

   Rather than re-invent the wheel trying to write an ARM random number
gernerator function, i thought i'd ask if anyone has done this before or if
there is an easy fast way to achieve random numbers.

   I'm thinking of doing a GBA conversion of the classic Atari 8bit version of
River Raid, which generates terrain and enemies randomly.

   Cheers,

   McGeezer

         Yahoo! Groups Sponsor
               ADVERTISEMENT




   Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.

Three words: Linear Congruental Generator

Graeme Cowie wrote:
> Hi gbadev forum,
>
> Rather than re-invent the wheel trying to write an ARM random number
> gernerator function, i thought i'd ask if anyone has done this before or
> if there is an easy fast way to achieve random numbers.
>
> I'm thinking of doing a GBA conversion of the classic Atari 8bit version
> of River Raid, which generates terrain and enemies randomly.
>
> Cheers,
>
> McGeezer
>
> *Yahoo! Groups Sponsor*
> ADVERTISEMENT
>
<http://rd.yahoo.com/SIG=12ckv5dmt/M=267637.4116730.5333196.1261774/D=egroupweb/\
S=1705055196:HM/EXP=1071087444/A=1853618/R=0/*http://www.netflix.com/Default?mqs\
o=60178338&partid=4116730>
>
>
> Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service
> <http://docs.yahoo.com/info/terms/>.


--
http://dreamcache.mine.nu

Do bear in mind that if you test the speed of the BIOS functions on an
emulator the result will not necessarily be indicative of what happens on
real hardware. The emulators generally just do a sqrt in native 80x86 code
and return the result.

Graham

-----Original Message-----
From: Thomas [mailto:sorcererxiii@...]
Sent: 09 December 2003 16:23
To: gbadev@yahoogroups.com
Subject: [gbadev] Re: Fixed Point Square Root


Ok, testing has revealed that the bios function is a good 10 times
faster than the 2.30 function (I didn't measure it precisely - all I
need to know is that it's faster).  To get more precision, I multiply
the input by 4096 then divide the result by sqrt(4096).

(Sqrt(fixedval << 12) << 5) >> 6

Of course, this limits us to a max input of 512.0, which is
sufficient for what it's being used.

Tom


--- In gbadev@yahoogroups.com, "Thomas" <sorcererxiii@y...> wrote:
> Thanks, I'll try that out . . . for some reason my brain is not
> working on this issue (years of only having to press the square
root
> key on a calculator?).  I also figured out that I can use the bios
> square root (I think) by realizing that
>
> sqrt(n * 1024) = sqrt(n)*sqrt(1024) = sqrt(n) << 5.
>
> I'll need to compare to see which method is faster/more accurate.
>
> Tom
>
>
> --- In gbadev@yahoogroups.com, "Damian Yerrick" <d_yerrick@h...>
> wrote:
> > --- In gbadev@yahoogroups.com, "Thomas" <sorcererxiii@y...> wrote:
> > > I'd like a general algorithm in C or psuedocode that could be
> > > used for different fraction sizes just be changing a #define
> > > value.  I've searched and found some that worked for specific
> > > cases (like one that was 2.30)
> >
> > For reference, here's an example of a 2.30 square root function:
> > http://www.worldserver.com/turk/opensource/FractSqrt.c.txt
> >
> > > but I could figure out how to adapt it for 22.10.
> >
> > The given code gives sqrt(1<<30) == 1<<30.  You want
> > sqrt(1<<10) == 1<<10 and sqrt(1<<30) == 1<<20.  So use the
> > 2.30 code and just shift the result right by 10 binary places.
> > In general, if you have n fractional places (in your case 10),
> > where n is odd and 0 <= n <= 30, then shift right by (30-n)/2
> > after calling the 2.30 routine.
> >
> > Division is rather slow on ARM; don't use the division based
> > Newton's method code that somebody else just posted.
> >
> > --
> > Damian



Yahoo! Groups Sponsor
ADVERTISEMENT




Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.

Ok, testing has revealed that the bios function is a good 10 times
faster than the 2.30 function (I didn't measure it precisely - all I
need to know is that it's faster).  To get more precision, I multiply
the input by 4096 then divide the result by sqrt(4096).

(Sqrt(fixedval << 12) << 5) >> 6

Of course, this limits us to a max input of 512.0, which is
sufficient for what it's being used.

Tom


--- In gbadev@yahoogroups.com, "Thomas" <sorcererxiii@y...> wrote:
> Thanks, I'll try that out . . . for some reason my brain is not
> working on this issue (years of only having to press the square
root
> key on a calculator?).  I also figured out that I can use the bios
> square root (I think) by realizing that
>
> sqrt(n * 1024) = sqrt(n)*sqrt(1024) = sqrt(n) << 5.
>
> I'll need to compare to see which method is faster/more accurate.
>
> Tom
>
>
> --- In gbadev@yahoogroups.com, "Damian Yerrick" <d_yerrick@h...>
> wrote:
> > --- In gbadev@yahoogroups.com, "Thomas" <sorcererxiii@y...> wrote:
> > > I'd like a general algorithm in C or psuedocode that could be
> > > used for different fraction sizes just be changing a #define
> > > value.  I've searched and found some that worked for specific
> > > cases (like one that was 2.30)
> >
> > For reference, here's an example of a 2.30 square root function:
> > http://www.worldserver.com/turk/opensource/FractSqrt.c.txt
> >
> > > but I could figure out how to adapt it for 22.10.
> >
> > The given code gives sqrt(1<<30) == 1<<30.  You want
> > sqrt(1<<10) == 1<<10 and sqrt(1<<30) == 1<<20.  So use the
> > 2.30 code and just shift the result right by 10 binary places.
> > In general, if you have n fractional places (in your case 10),
> > where n is odd and 0 <= n <= 30, then shift right by (30-n)/2
> > after calling the 2.30 routine.
> >
> > Division is rather slow on ARM; don't use the division based
> > Newton's method code that somebody else just posted.
> >
> > --
> > Damian

Thanks, I'll try that out . . . for some reason my brain is not
working on this issue (years of only having to press the square root
key on a calculator?).  I also figured out that I can use the bios
square root (I think) by realizing that

sqrt(n * 1024) = sqrt(n)*sqrt(1024) = sqrt(n) << 5.

I'll need to compare to see which method is faster/more accurate.

Tom


--- In gbadev@yahoogroups.com, "Damian Yerrick" <d_yerrick@h...>
wrote:
> --- In gbadev@yahoogroups.com, "Thomas" <sorcererxiii@y...> wrote:
> > I'd like a general algorithm in C or psuedocode that could be
> > used for different fraction sizes just be changing a #define
> > value.  I've searched and found some that worked for specific
> > cases (like one that was 2.30)
>
> For reference, here's an example of a 2.30 square root function:
> http://www.worldserver.com/turk/opensource/FractSqrt.c.txt
>
> > but I could figure out how to adapt it for 22.10.
>
> The given code gives sqrt(1<<30) == 1<<30.  You want
> sqrt(1<<10) == 1<<10 and sqrt(1<<30) == 1<<20.  So use the
> 2.30 code and just shift the result right by 10 binary places.
> In general, if you have n fractional places (in your case 10),
> where n is odd and 0 <= n <= 30, then shift right by (30-n)/2
> after calling the 2.30 routine.
>
> Division is rather slow on ARM; don't use the division based
> Newton's method code that somebody else just posted.
>
> --
> Damian

--- In gbadev@yahoogroups.com, "Thomas" <sorcererxiii@y...> wrote:
> I'd like a general algorithm in C or psuedocode that could be
> used for different fraction sizes just be changing a #define
> value.  I've searched and found some that worked for specific
> cases (like one that was 2.30)

For reference, here's an example of a 2.30 square root function:
http://www.worldserver.com/turk/opensource/FractSqrt.c.txt

> but I could figure out how to adapt it for 22.10.

The given code gives sqrt(1<<30) == 1<<30.  You want
sqrt(1<<10) == 1<<10 and sqrt(1<<30) == 1<<20.  So use the
2.30 code and just shift the result right by 10 binary places.
In general, if you have n fractional places (in your case 10),
where n is odd and 0 <= n <= 30, then shift right by (30-n)/2
after calling the 2.30 routine.

Division is rather slow on ARM; don't use the division based
Newton's method code that somebody else just posted.

--
Damian