Minimad code size

Hello,
 We are currently trying to develop an arm-mp3 player. (
http://groups.google.com/group/qamp/, not very interesting really)
 Problem is, the code size generetad by arm-elf-gcc is about 300k, while all
the different object files are about 100k. We already worked around the
rq_table.dat using a Taylor approximation. The problem is we only have 128k
flash available (we use a real embedded system, not some sort of arm with
megs of memory and some weird linux kernel ;))
 We started developing under windows (Dev-C++), trying to get to know mad.
We were able to decode an mp3 file to pcm without much trouble. The windows
executable however, is only 181k, and that includes rq_table.dat.
 We already tried using -o2 for gcc and strip, but that didn't get us very
far. Neither do we include any unnecessary files (layer12.c, sys/*.h, etc).
 Any help would be appreciated as we pretty much have given up on this
ourselves...
 Tiemen Schut