On Fri, 29 Jul 2005, Michal Schmidt wrote: > Rafael J. Wysocki wrote: > > On Friday, 29 of July 2005 21:46, Michal Schmidt wrote: > > > >>The function calc_nr uses an iterative algorithm to calculate the number > >>of pages needed for the image and the pagedir. Exactly the same result > >>can be obtained with a one-line expression. > > > > > > Could you please post the proof? > > > > Rafael > > OK, attached is a proof-by-brute-force program. It compares the results > of the original function and the simplified one. Here's a more general proof. As I understand it, calc_nr is given nr_copy, the number of data pages that need to be written out, and it has to return the number of pages needed to hold the image data plus a bunch of PBE pagedir indexes, where each page gets one index (and pages containing PBEs need their own indexes as well). For brevity, let n = nr_copy, let p = PBES_PER_PAGE, and let x be the number of pagdir pages needed. Since each page can hold p PBEs, there will be room to store px PBEs. The total number of pages is n + x, so the routine needs to find the smallest value of x for which px >= n + x or (p-1)x >= n or x >= n / (p-1). The obvious solution is x = ceiling(n / (p-1)), so calc_nr should return n + ceiling(n / (p-1)), which is exactly what Michal's patch computes. Alan Stern
