Or a Whale, II

Tomorrow’s flowers are in the seeds of today.

Chinese proverb

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void strins(char * s, char i, size_t pos)
 {
  memmove(s+pos+1,s+pos,strlen(s+pos)+1);
  s[pos]=i;
 }


int main()
 {
  char buffer[30]="mti ie l";
  char deleted[]="eenhakst s wekas ili";

  srand(12345);

  for (int i=0;i<20;i++)
   {
    strins(buffer,deleted[i],rand() % strlen(buffer));
    printf("%s\n",buffer);
   }

  return 0;
 }

As for last week’s entry, your task is to explain how it works (although rather not complicated).

*
* *

If it doesn’t work for you, use gcc 4.4+, glibc 2.9+, or if it fails, check it out on ideone.

2 Responses to Or a Whale, II

  1. drfrankenstein90 says:

    rand() does not return a random number, it returns a pseudo-random number. Its behaviour is therefore predictable and consistent when srand() is called with a constant value.

    With such a behaviour, it takes just a bit of analysis to build an input that can be transformed to something predictable using that generator.

    More specifically, glibc implements rand() as a linear congruential generator with a modulus of 2^32, a multiplier of 1103515245 and an increment of 12345.

    Does seeding the generator with its increment has a particular effect I didn’t know about?

    ——-

    Excerpt from “ISO/IEC 9899: Programming languages — C, Second edition”:

    “The srand function uses the argument as a seed for a new sequence of pseudo-random
    numbers to be returned by subsequent calls to rand. If srand is then called with the
    same seed value, the sequence of pseudo-random numbers shall be repeated.”

    • Steven Pigeon says:

      The behavior of the pseudo-random generator is predictible if, and only if, you have all the information about its internal state. While in previous versions of gcc it seemed to use a basic LCG, in the version I have it uses a considerably more elaborate generator.

      Glibc 2.9.x is found at http://ftp.gnu.org/gnu/glibc/

      Inspecting the code for rand() you see it’s quite the usine à gaz:

      /* If we are using the trivial TYPE_0 R.N.G., just do the old linear
         congruential bit.  Otherwise, we do our fancy trinomial stuff, which is the
         same in all the other cases due to all the global variables that have been
         set up.  The basic operation is to add the number at the rear pointer into
         the one at the front pointer.  Then both pointers are advanced to the next
         location cyclically in the table.  The value returned is the sum generated,
         reduced to 31 bits by throwing away the "least random" low bit.
         Note: The code takes advantage of the fact that both the front and
         rear pointers can't wrap on the same call by not testing the rear
         pointer if the front one has wrapped.  Returns a 31-bit random number.  */
      
      int
      __random_r (buf, result)
           struct random_data *buf;
           int32_t *result;
      {
        int32_t *state;
      
        if (buf == NULL || result == NULL)
          goto fail;
      
        state = buf->state;
      
        if (buf->rand_type == TYPE_0)
          {
            int32_t val = state[0];
            val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
            state[0] = val;
            *result = val;
          }
        else
          {
            int32_t *fptr = buf->fptr;
            int32_t *rptr = buf->rptr;
            int32_t *end_ptr = buf->end_ptr;
            int32_t val;
      
            val = *fptr += *rptr;
            /* Chucking least random bit.  */
            *result = (val >> 1) & 0x7fffffff;
            ++fptr;
            if (fptr >= end_ptr)
      	{
      	  fptr = state;
      	  ++rptr;
      	}
            else
      	{
      	  ++rptr;
      	  if (rptr >= end_ptr)
      	    rptr = state;
      	}
            buf->fptr = fptr;
            buf->rptr = rptr;
          }
        return 0;
      
       fail:
        __set_errno (EINVAL);
        return -1;
      }
      

      So it’s not always the linear congruential generator that gets called. In my version of “methinks it is like a weasel” (and Ideone’s) uses the complicated generator.

      This being said, you’re quite right about predictability. Now, we only have to find a way to exploit the information contained in the random sequence to do actual work (but I guess there’sn’t much we can do).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 65 other followers

%d bloggers like this: