IPF Library: Optimisations

28 Janurary 2005

Density Map

Optimized the density map code a bit. The density map allocated by the IPF Library is now one unit larger than the size needed, which eliminates a check for boundary overflow every 8 bits. Not a massive optimisation, but it helps.

Iterating Cycles

We could not find out how to iterate the next cycle without using floating point arithmetic or losing our cycle exact precision. The method now uses some interpolation, but the results are correct. The main thing is that they are not simply estimates to prevent rounding errors from happening, as this could cause a loss of sync.

To put that another way, there are known key coordinates of the speed curve at certain intervals (for every complete byte to save memory), and the points in between are interpolated in way that ensures proper distribution.

Lock Time Optimisations

The FdcLockTime function of the library is pretty special too. It uses the new fraction based density map, and performs a binary search to find the estimated point on a track based on the elapsed clock cycles from the disk rotation, then a linear search to find the correct bit position. Of course, binary searches are not normally used to find non-exact values or estimates - this is a rather customised use of the algorithm.

This makes it possible to “lock” onto the data stream on the rotating disk with just 14+4 compares on average. Without this, it would take roughly 50000 compares on average. Another, probably worse solution, would be to use a huge multi-megabyte lookup table.