Advanced Algoithm issues to generate unique 6 char long code

I have used this algorithm to generate 100 codes. Now Once again i have searched the threads on this site and on google before posting. The algorthms found do work in generating the code the issue I got is i have to generate UNIQUE codes from the one i already have. The problem i am finding is all the scripts are all failing to execute.

So basically I have to generate 400 more voucher codes however while my algorithm's works it keeps timing out due to it taking to long to execute. I have tried several other algorithms from the threads on Stack overflow but for some reason they all keep timing out. I need advice on what i can do to my algorithm to actually produce 400 more unique 6 Char codes.

Here is script I have

/**
**Use this portion to get my current 100 codes in an array which i use
**/
$redeem = 'THIS IS A STRING WHICH CREATES AN ARRAY CONTIANING 100 VALUES'; 
$redeem = preg_replace('/\s+/', '', $redeem);
$redeem_code = str_split($redeem, 6);

/**
**Function generates unique 6 letter voucher codes
**
**/

        function random_str($length, $keyspace = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ')
        {
            $str = '';
            $max = mb_strlen($keyspace, '8bit') - 1;
            for ($i = 0; $i < $length; ++$i) {
            $str .= $keyspace[mt_rand(0, $max)];
            }
        return $str;
        }

/**
**This is the query which checks against my array and then echo's a valid code
**
**/
        $redeem_count = count($redeem_code);
        $i = 0;
        $ia = 1;
        while($i <= 500){

                $string = random_str(6);
                if(in_array($string, $redeem_code))
                {
                     echo $string;
                     $i= $i+1;
                }

        }

Constant Error Message on All functions tried.

Fatal error: Maximum execution time of 120 seconds exceeded in C:\wamp\www\nfr_chip.php on line 115