在开发MP3播放器的DSP程序的时候，我曾经遇到过这样一个问题：播放大文件时（100M以上）快退的速度很慢，但是快进没有问题。一般MP3文件很少大于100M，但是那个MP3播放器可以录制WAVE文件，一不小心就可能录制一个几百兆的大文件出来。

个 播放器采用Compact Flash卡存储文件，最新的CF卡的大小已经达到4G，而且有一种和CF兼容的Micro Drive已经做到了6G，所以用户甚至可以录制1G以上的大文件。CF卡采用FAT16或FAT32的文件系统，在DSP的程序中有一个库专门用来存取 FAT文件系统的数据。它提供的接口函数和C语言的fread,fwrite,fseek类似。而快进快退是调用fseek函数重新定位文件指针来实现 的，所以快退的速度取决于fseek函数往回拨文件指针的速度。

我们知道FAT文件系统的用文件分区表（FAT）来保存文件在磁盘上的存储 位置的信息的。每个文件对应一条在文件分区表中的链表。由于这个链表是单向的，所以只能从前往后遍历它，用fseek快进的时候，从链表的当前位置往后搜 索就可以了。但是若要从当前位置往前跳（快退），由于是单向链表，无法从当前位置往前搜索，因此只能从链表的头开始数起，一直数到指定的位置。当文件很 大，而且当前位置已经很靠后的时候，每快退一次，都要从链表头开始遍历几乎整个链表。链表储存在FAT中，而FAT在CF卡上，因此每次读取链表都需要访 问CF卡，这样做速度当然会很慢。

DSP的内存很小，也无法把整个链表读入内存中，因此我想了一个折中的办法：每隔50M保存一个链表的位 置，这样往回跳的时候就不需要从链表头开始搜索，而只需要从最近的一个保存点开始就行了。最后我让程序动态地决定两个保存点之间的距离，每个文件最多保存 20个点（需要20个long）。一开始每两个保存点的间隔为1M，当文件播放到21M需要保存第21个点的时候，就把前面的20个点压缩成10个，这样 就变为每2M保存一个点了。随着文件的播放，两个保存点之间的长度成倍地增加。