On 7/14/20 6:09 PM, Wolfgang Denk wrote:
Dear Heinrich,
In message 53dad1c7-7684-f975-1567-6ec5e03fa4b6@gmx.de you wrote:
If we want a fast algorithm to determine the last supported address even if the start or size is not a power of two:
Are you sure? How is this supposed to work?
Running it with start = 0 and size = 0xC0000000 it will test the memory locations
0x80000000 0xA0000000 0xB0000000 0xB8000000 0xBC000000 0xBE000000 0xBF000000 0xBF800000 0xBFC00000 0xBFE00000 0xBFF00000 0xBFF80000 0xBFFC0000 0xBFFE0000 0xBFFF0000 0xBFFF8000 0xBFFFC000 0xBFFFE000 0xBFFFF000 0xBFFFF800 0xBFFFFC00 0xBFFFFE00 0xBFFFFF00 0xBFFFFF80 0xBFFFFFC0 0xBFFFFFE0 0xBFFFFFF0 0xBFFFFFF8 0xBFFFFFFC 0xBFFFFFFE 0xBFFFFFFF
The last accessible byte is at 0xBFFFFFFF which matches (start + size - 1) in your example.
The difference to the current logic is that it does not require start or size to be power of two.
If the size input is larger than the actually accessible memory size, you will get the actual memory size, e.g. lets assume that the last accessible address is 0x3333:
int test(unsigned long addr) { int ret = addr < 0x3333;
printf("0x%lx - %s\n", addr, ret ? "success": "failed"); return ret; }
unsigned long start = 0x0000555UL; unsigned long size = 0xC0000013L;
The series of test locations will be:
0x8000000 - failed 0x4000000 - failed 0x2000000 - failed 0x1000000 - failed 0x800000 - failed 0x400000 - failed 0x200000 - failed 0x100000 - failed 0x80000 - failed 0x40000 - failed 0x20000 - failed 0x10000 - failed 0x8000 - failed 0x4000 - failed 0x2000 - success 0x3000 - success 0x3800 - failed 0x3400 - failed 0x3200 - success 0x3300 - success 0x3380 - failed 0x3340 - failed 0x3320 - success 0x3330 - success 0x3338 - failed 0x3334 - failed 0x3332 - success 0x3333 - failed
Now the algorithm returns that the last accessible memory location is 0x3332.
With unsigned long start = 0x0000555UL; unsigned long size = 0x800L;
0x800 - success 0xc00 - success 0xd00 - success 0xd40 - success 0xd50 - success 0xd54 - success
The last accessible memory location is 0xd54 (0x555 + 0x800 - 0x1).
The algorithm runs in O(log(UINT_MAX)) which is the same time complexity as for the current algorithm.
Best regards
Heinrich
What do you intend with such a sequence?
Best regards,
Wolfgang Denk