On 7/14/20 6:09 PM, Wolfgang Denk wrote:
> Dear Heinrich,
>
> In message <53dad1c7-7684-f975-1567-6ec5e03fa...@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
>
