#166815 - Flash - Thu Feb 19, 2009 2:02 pm
Having a slight problem trying to reduce a 32 bit number returned from a generator to a value between 0-383.
| Code: |
ldr ip, seedpointer
ldmia ip, {r8, r9}
tst r9, r9, lsr #1
movs r2, r8, rrx
adc r9, r9, r9
eor r2, r2, r8, lsl #12
eor r8, r2, r2, lsr #20
stmia ip, {r8, r9}
..... with these variables :-
seedpointer:
.long seed
seed:
.long 0x55555555
.long 0x55555555
|
is used to generate the number with r8 returning the value. No matter what i do, i cannot get the result within my bounds without creating weighting to either of the ends due to my rounding?
I am sure it is something silly that I am missing, but for the life of me, I cannot get it right :(
Any help would be great
#166826 - Miked0801 - Thu Feb 19, 2009 6:40 pm
Lets see
Load r12 with your seed pointer
then grab 64-bits of seed into r8,r9
Then put the low bit of r9 on carry
Then move into r2, r8 with something called rrx?
Mix and munge r2,r9,r8
and put a new seed back out.
I see nothing - nothing at all that is limiting the range of generator. You are going to get some sort of number in r8 for sure, but it will be 32-bit.
You could range it without a mod/divide with:
| Code: |
and r0,r8,#0x1FF ; Get a number 0 - 511
add r0,r8,r8,lsl #1 ; x3
mov r8,r8, lsl #4 ; / 4
|
And you get a number from 0 to 383
#166830 - naleksiev - Thu Feb 19, 2009 7:15 pm
| Miked0801 wrote: |
| Code: |
and r0,r8,#0x1FF ; Get a number 0 - 511
add r0,r8,r8,lsl #1 ; x3
mov r8,r8, lsl #4 ; / 4
|
And you get a number from 0 to 383 |
I just start learning ASM for ARM so excuse me if I'm wrong but I think there are a few errors in above code.
Shouldn't it be
and r0,r8,#0x1FF ; Get a number 0 - 511
add r8,r0,r8,lsl #1 ; x3
mov r8,r8, rsl #4 ; / 4
_________________
http://raynds.blogspot.com/
#166832 - Maxxie - Thu Feb 19, 2009 8:16 pm
indeed,
on top of that:
- exchange the #4 against a #2 if /4 is meant.
at the second add, use r0 at both inputs. r8 is still the full range at that point (>511)
_________________
Trying to bring more detail into understanding the wireless hardware
#166833 - Cearn - Thu Feb 19, 2009 8:53 pm
If your random number generator spans the whole 32 bits (or even just the top N bits), you use something like this:
| Code: |
@ Assume r2 is an RNG in range[0, 1<<32). Wanted is range [0, 384)
ldr r1,=384 @ Load desired range.
mull r3, r0, r1, r2 @ r0 = 384*[0, 1<<32)/(1<<32) for [0, 384) result.
|
Basically, an N-bit RNG has range [0, 1<<N). Multiplying by your range M gives the range [0, M<<N). shifting right by N reduces it to [0, M).
#166836 - Flash - Thu Feb 19, 2009 9:40 pm
| Maxxie wrote: |
indeed,
on top of that:
- exchange the #4 against a #2 if /4 is meant.
at the second add, use r0 at both inputs. r8 is still the full range at that point (>511) |
this works, thanks
| Code: |
ldr r2,=0x1ff
and r9,r8,r2
add r8,r9,r9,lsl #1
mov r8,r8,lsr #2
|
I had to change the registers as was using r0 in the loop.
I tried the tidy looking mul version, but cannot compile with a mul stretching 4 registers
#166843 - Cearn - Fri Feb 20, 2009 10:27 am
| Flash wrote: |
| I tried the tidy looking mul version, but cannot compile with a mul stretching 4 registers |
I thought the unsigned long multiply was called MULL, but apparently it's UMULL. Try that instead. See also gbatek:MUL for details.
#166853 - Miked0801 - Fri Feb 20, 2009 7:45 pm
Wow, I screwed up every single line. Go me.
Bah, and to 0-511, Multiply by 3, divide by 4. There. Silly programmer, asm tricks are for kids (with assemblers to check ones work...)
#166854 - Flash - Fri Feb 20, 2009 8:49 pm
| Miked0801 wrote: |
Wow, I screwed up every single line. Go me.
Bah, and to 0-511, Multiply by 3, divide by 4. There. Silly programmer, asm tricks are for kids (with assemblers to check ones work...) |
Thanks for showing me the way! :)
The main thing was it got the job done, thanks!!
#167403 - Flash - Tue Mar 10, 2009 11:01 pm
Ok, got another little problem,
Using the code at the top of this post to return a random 32 bit number, does anyone know the quickest way to reduce it to a number from 0-223?
I have sat here for ages and can get the range but it is messy! I am sure that there is a really easy way to do it, but again... for the life of me :)
#167404 - Miked0801 - Tue Mar 10, 2009 11:05 pm
32-bits to 8-bits =
>> 24
8-bits = 0-255 (or 256 entries)
224 / 256 = 7/8
* 7,
>> 3
#167410 - Ruben - Wed Mar 11, 2009 2:11 am
Neat algorithm..
Simple, fast, hard to figure out without seeing it and too easy when you do. I love it.