Author Topic: fnRandom() not changing  (Read 28911 times)

Offline alager

  • Jr. Member
  • **
  • Posts: 92
    • View Profile
fnRandom() not changing
« on: April 28, 2009, 04:52:36 PM »
When I run my code on the simulator the fnRandom() call returns a random number.  However when I run it on the target MCF52233CAF, I get the same number over and over again: 32767.
I even tried calling fnInitialiseRND() right before it each time...same number.

Any ideas?

Thanks,
Aaron
« Last Edit: April 28, 2009, 04:56:03 PM by alager »

Offline mark

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 3240
    • View Profile
    • uTasker
Re: fnRandom() not changing
« Reply #1 on: April 28, 2009, 05:57:19 PM »
Hi Aaron

Are you calling the function several times after each other when the code is running or just once, with a board reset in-between?

Assuming the first case I can't imagine how this can have problems unless some memory is being overwritten between calls.
The M52233 has no HW based random number generator (as the M52235 does, for example) and so will use the following code:

    register unsigned short usShifter = usRandomNumber;                  // for speed, copy to register

    usShifter >>= 1;                                                     // increments the decoding key using predefined generator pattern

    if (((usShifter & FEEDBACK1) && (usShifter & FEEDBACK2)) ||
        (((!(usShifter & FEEDBACK1)) && (!(usShifter & FEEDBACK2))))) {
        usShifter |= FEEDBACKIN;                                         // 1 fed back
    }
    usRandomNumber = usShifter;

    return (usShifter);


When the code is exited, the new value is saved to usRandomNumber (a static variable which is initialised with a random value on reset/powerup). This means that on subsequent calls the new value should be used as input to the next iteration.
The only explanation that I have for the number always being the same is when the value usRandomNumber  is being overwritten between calls - setting back the same value each time, resulting in the same random number.

Could you check whether this could be the case (on entry you should always find the last generated number).
I did some tests with the random number generator (with and without HW support) quite recently and didn't notice any problems.

I have in fact prepared an improvement of the random behavior between warm resets (in next SPs) but this is not related to your case.

Note also that, if the code were to try to use the HW based random number generator it would cause a memory access violation so I don't expect a problem with configurations concerning this.

Regards

Mark

Offline alager

  • Jr. Member
  • **
  • Posts: 92
    • View Profile
Re: fnRandom() not changing
« Reply #2 on: April 28, 2009, 06:23:58 PM »
Mark,

These two lines are located in the TCP_EVENT_CONNECTED case:
Code: [Select]
fnInitialiseRND();
rnd = fnRandom(); //rnd is an unsigned short

So yes it is called repetitively.  I read the comments in that function and tried the reset button, to see if it would induce a change, but it didn't.
My stack and heap seem okay:
HEAP   Free 0x061c from 0x5400
STACK   Unused 0x1aff

I'll see what I can see in the hardware...I'm using a reduced pin package, so sometimes I can't see what I want.

Aaron

Offline mark

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 3240
    • View Profile
    • uTasker
Re: fnRandom() not changing
« Reply #3 on: April 28, 2009, 06:58:10 PM »
Hi Aaron

When testing, remove the fnInitialiseRND() since it will cause the priming value to be set again each time and then really give the same value.

Regards

Mark


Offline alager

  • Jr. Member
  • **
  • Posts: 92
    • View Profile
Re: fnRandom() not changing
« Reply #4 on: April 28, 2009, 07:01:36 PM »
Mark,

What I can see is usRandomNumber is started with 0xffff in fnRandom().  This gets put into usShifter and shifter to the right by 1. => uShifter now has 0x7fff
Then if
#define FEEDBACK1         0x0001                                         // feedback pattern for 16 bit shift register
#define FEEDBACK2         0x0002
are both set or both not set, then set
#define FEEDBACKIN        0x4000                                         // 15 bits used
which takes us back to 0x7fff.

On the next loop through, we start at 0x7fff, shift to 0x3fff, the if is true so OR in the feedback and end up at 0x7fff again.

I traced back to *ptrSeed, which is starting this off at 0xffff after fnInitialiseRND()

Aaron

PS. This all happens regardless if I call the fnInitialiseRND() or not.  I just did it both ways.
« Last Edit: April 28, 2009, 07:06:03 PM by alager »

Offline mark

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 3240
    • View Profile
    • uTasker
Re: fnRandom() not changing
« Reply #5 on: April 28, 2009, 08:21:36 PM »
Hi Aaron

You have indeed found a bug in the pseudo-random number primer. If the start value is either 0x7fff or '0xffff it causes it to stick in a loop with value 0x7fff.

The random number generator (PRNG) s a standard feedback shift register sequencer. It is of 15 bits ling, with feedback taps at m = 15 and n = 14, giving a pseudo-random sequence length of 32767 before the pattern repeats. Also the value 0x0000 should be avoided since it gets stuck.

So I just verified. The pattern generated by the code repeats after 11810 values (lower than it should) and gets stuck not at 0x0000 but when all used bits are '1', which is the inverse.

Something must therefore be wrong with the algorithm...

The first thing that I found was that the exclusive OR used to feed back in the algorithm is incorrect - it has a polarity error.
For a quick fix you can use the following correction:

    if (((usShifter & FEEDBACK1) && (!(usShifter & FEEDBACK2))) ||
        (((!(usShifter & FEEDBACK1)) && (usShifter & FEEDBACK2)))) {
        usShifter |= FEEDBACKIN;                                         // 1 fed back
    }



Here the check of FEEDBACK2 has been inverted in each case.
This then gave a pseudo-random sequence of 16'383 as long as zero is avoided (the code already avoid this) and 0x7fff or 0xffff primes don't cause problems.

However I believe that it should still do more. I will post a modification to achieve 64k sequencing (should be possible with three taps according to my boot) as soon as I have verified it.

Thanks for finding this problem since I had never doubted the PRNG since it has been used for such a ling time...

regards

Mark





Offline mark

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 3240
    • View Profile
    • uTasker
Re: fnRandom() not changing
« Reply #6 on: April 28, 2009, 08:56:53 PM »
Hi Aaron

I found an algorithm for generating a 65535 number sequence: http://en.wikipedia.org/wiki/Linear_feedback_shift_register


In uTasker.c

#define PRNG_POLY  0xb400                                                // taps: 16 14 13 11; characteristic polynomial: x^16 + x^14 + x^13 + x^11 + 1

extern unsigned short fnRandom(void)
    #ifdef RND_HW_SUPPORT
    return fnGetRndHW();                                                 // get a random value from the hardware
    #else
    register unsigned short usShifter = usRandomNumber;                  // for speed, copy to register
    usShifter = (usShifter >> 1) ^ (-(signed short)(usShifter & 1) & PRNG_POLY);
    usRandomNumber = usShifter;
    return usShifter;
    #endif
}


This is very efficient and utilises all 16 bits of the short word. Again 0x000 must be avoided as prime value (otherwise it sticks there).

Have a go with this and I will commit the improvement ready for the next SP release. This is also not Coldfire specific so I will add a link to this from the general forum topic.

Many thanks also to the French mathematician Galois since the maths is beyond me...

Regards

Mark


Offline alager

  • Jr. Member
  • **
  • Posts: 92
    • View Profile
Re: fnRandom() not changing
« Reply #7 on: April 29, 2009, 09:54:10 PM »
Thanks Mark!  I too looked on wikipedia, but wasn't into the math...

Aaron

Offline alager

  • Jr. Member
  • **
  • Posts: 92
    • View Profile
Re: fnRandom() not changing
« Reply #8 on: July 02, 2010, 06:44:09 PM »
Mark,

The sequence generated by the algorithm works great, however the seed value is very consistent.  The random pointer ptrSeed, is always the same value (0) and therefore fnInitialiseRND() returns 0x127b.
This may have to do with the compactness of my project, and not touching the memory space that the pointer is getting assigned to.

Have you or anyone else played with using network data to get a more randomized seed?  Or some other method? 

Thanks,
Aaron

Offline mark

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 3240
    • View Profile
    • uTasker
Re: fnRandom() not changing
« Reply #9 on: July 02, 2010, 11:09:19 PM »
Hi Aaron

There is an error in the priming of the random number in the present Coldfire project. This results in the same start value after every reset and every power up. However this can be solved quite easily by doing the following (first some explanations and then the solution):

1) The idea is that the value used is a random SRAM value after a power up. The SRAM does indeed behave quite randomly in some processors but other types may tend to power up with a similar, or same, value each time.

2) The random SRAM location is created by simply assigning an uninitialised value on stack (an area of memory not initialised in any way). The value is changed each time that a new random number is generated and should survive between warm resets. When powered up again it will be uninitialised and so tend to be random in nature.

3) The potential problems are:
- the compiler "may" initialise the value to zero, which is not desired in this case
- if the stack is used before the random location is created (by calling a sub-routine that uses it) it will possibly get set to a constant value each time
In the case of the Coldfire project (each one will be checked before next releases) it seems that one of the above is true and so resulting in the same primed value.

4) In the case of the Coldfire project it can be solved by modifying the following lines in m5223x.c (start of main()):
#define RANDOM_SEED_LOCATION (unsigned short *)(START_OF_SRAM + SIZE_OF_RAM - 4)
//unsigned short usRandomSeed; comment out
ptrSeed = RANDOM_SEED_LOCATION; // &usRandomSeed - no longer use &usRandomSeed but instead use RANDOM_SEED_LOCATION


Making sure that SIZE_OF_RAM really matches the size of the SRAM in the specific chip, RANDOM_SEED_LOCATION is then the very last long word in the SRAM.

The other change needed is in the linker script file that is used:

___SP_INIT   = ___SRAM + ___SRAM_SIZE;
becomes
___SP_INIT   = ___SRAM + ___SRAM_SIZE - 4;


The stack pointer starts at one long word below the end of SRAM and so it ensures that the random number location is really never used by stack.


However whether the method is adequate depends on the processor used (how random the power up value is). In the case of chips with HW based random number generation this is used instead - in some cases also an ADC input with a noise generator connected has been used. There are also external chips (eg. I2C based) which can be used to generate highly random numbers according to requirements for some security algorithms.

Unfortunately the M5223X has SRAM which tends to have a fixed start value (according to my M52233DEMO and M52235EVB boards and practical tests). However the value at each processor does seem to be different, so that is a positive point...

Regards

Mark





Offline alager

  • Jr. Member
  • **
  • Posts: 92
    • View Profile
Re: fnRandom() not changing
« Reply #10 on: July 14, 2010, 12:30:04 AM »
This may sound dumb, but how do I know which linker script is being used by code warrior?

Thanks,
Aaron

Offline mark

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 3240
    • View Profile
    • uTasker
Re: fnRandom() not changing
« Reply #11 on: July 14, 2010, 12:51:50 AM »
Hi Aaron

When you select a target in CW you will see all of the linker scripts but only one of them will be active. There will be a DOT next to the one being used and so the DOT will change as the target is changed (as long as different linker scripts are needed for each). This is controlled in the target properties where some files are excluded form the build - excluding a file from the build (can also be a c-file) will cause the DOT next to it to disappear.

Regards

Mark


Offline alager

  • Jr. Member
  • **
  • Posts: 92
    • View Profile
Re: fnRandom() not changing
« Reply #12 on: July 14, 2010, 05:21:06 PM »
Mark,

The simulator is unhappy with these latest changes.  I'm getting an access violation when trying to access the new location of *ptrSeed in fnInitialiseRND():
unsigned short usRnd = *ptrSeed;


Offline mark

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 3240
    • View Profile
    • uTasker
Re: fnRandom() not changing
« Reply #13 on: July 14, 2010, 06:29:46 PM »
Hi Aaron

If you look in the code you will see two positions for this initisialisation. One is used by the simulator [EXTERNSTATIC void fnInitHW(void)] and one by the target [extern int main(void)].

The change should only be made in the target part. The simulator part doesn't need to be changed since it can't work identically . In my code I have a comment to this effect "note that the target works differently"

Regards

Mark


Offline alager

  • Jr. Member
  • **
  • Posts: 92
    • View Profile
Re: fnRandom() not changing
« Reply #14 on: July 15, 2010, 07:24:21 PM »
Mark,

For our case we need the seed value to be more random than just between chips, we need it to be more random on each power cycle.
Also we are mostly concerned with using the random value for network traffic stuff.  So here is what I did.  It's much more random, but does rely on network traffic.  So a project that doesn't use networking will not benefit from this method.

In NetworkIndicators.c declare an unsigned short randomSeed  and in the EMAC_RX_INTERRUPT case:
ACTIVITY_LED_ON();                                      // turn on activity LED (for a short time)
randomSeed = (randomSeed * randomSeed) + 1;// start forming a random seed, based on local network traffic.

then in fnRandom() add:
register unsigned short usShifter = usRandomNumber;  // for speed, copy to register
if (!usShifter) {
         if(randomSeed){
            usShifter = randomSeed;
         }else{
            usShifter = 0x127b;               //should never happen, but just in case
         }
      }
}


lastly I stubbed out fnInitialiseRND() to just return 0.

This method works pretty well.  The first time fnInitialiseRND() is called, randomSeed is still zero, but by the time fnRandom() is called for the first time, there has been some network traffic and randomSeed now has some 16 bit number.

Aaron