Configuration on Cyclone III

You're right about the configuration data size listed in the handbook--there's a note that specifies that the sizes are preliminary. If you're just looking for an estimate, though, I've got to think that the listed values are plus-or-minus ten percent. Hopefully we'll get exact numbers soon.

Remote Update supports both AS and AP configuration. Decompression is supported in AS and PS. So if you want to do both, it looks like you're forced into AS.

Decompression does complicate the calculation, since the amount of compression done is not deterministic. You might assume the configuration file will be compressed by 50%.

So . . . take the estimated file size for your Cyclone III part, divide it by 2, and that's the number of clock cycles you'll need.