Algoritmi: script in PHP, Javascript, C

Questo articolo è stato scritto da gabryhacker.
Le funzioni illustrate codificano una stringa in un valore binario, corrispondente ai codici ASCII dei singoli caratteri della stringa, e viceversa.

mixed str2bin(string $str[, int $mode = 0]);
string bin2str(mixed $bin);

Script:

<?php

function str2bin($str, $mode = 0){
    $out = false;
    if($mode < 0 || $mode > 2)
    return false;
    for($a=0; $a<strlen($str); $a++){
        $dec = ord(substr($str, $a, 1));
        $bin = '';
        for($i=7; $i>=0; $i--)
            if ($dec >= pow(2, $i)) {
                $bin .= "1";
                $dec -= pow(2, $i);
            }else
                $bin .= "0";
        switch($mode){
            case 1:
                $out .= $bin;
                break;
            case 0:
            case 2:
                $out[$a] = $bin;
                break;
        }
    }
    if($mode == 0)
        $out = join(" ", $out);
    return $out;
}

function bin2str($bin){
    if(is_array($bin))
        $explo = $bin;
    else{
        $explo = str_replace(" ", "", $bin);
        $explo = str_split($explo, 8);
        $explo = explode(" ",$explo);
    }
    for($i=0; $i<count($explo); $i++)
        $as[] = chr(bindec($explo[$i]));
    return join("", $as);
}

?>

La funzione str2bin() accetta due parametri: $str e $mode. $mode è facoltativo, e per default è impostato a zero. Il parametro $mode riguarda il valore di ritorno della funzione. Codificando la parola ‘ciao’, ecco i vari casi:

echo str2bin("ciao"); // 01100011 01101001 01100001 01101111
echo str2bin("ciao", 1); // 01100011011010010110000101101111
echo str2bin("ciao", 2); // Array

Come si vede, settando $mode a 2 otterremo un array (gli elementi dell’array sono le codifiche dei singoli caratteri, ndr).

La funzione bin2str() accetta solo il parametro contenente la stringa binaria da decodificare. Questa stringa può essere di tre tipi, precisamente i tre tipi di valore ritornati da str2bin().
Ecco degli esempi. Decodificando la codifica di ‘ciao’ nei tre modi sopra visti otteniamo:
echo bin2str(”01100011 01101001 01100001 01101111″); // ciao
echo bin2str(”01100011011010010110000101101111″); // ciao
echo bin2str(str2bin(”ciao”, 2)): ciao
Nel terzo esempio ho passato str2bin() che restituisce un array (in questo caso array("01100011","01101001","01100001","01101111"), ndr).
Come vediamo, bin2str() riesce a decodificare i tre tipi di codifica forniti da str2bin().
Spero che queste due funzioncine siano utili.

<- Parte I

Il codice è un po’ lungo perchè ci sono diverse funzioni, ma è comunque facile da capire.

Primo passo: eliminare gli zeri.

 72    function base2no0($num = 0, $base = 10){
 73        $q = $num;
 74        $ord = 0;
 75        while($q>0){
 76            $q = floor($q/($base-1));
 77            $num += pow($base,$ord)*$q--;
 78            $ord++;
 79        }
 80        $num++;
 81        return $num;
 82    }
 83
 84    function no0tobase($num = 1, $base = 10){
 85        if($num%$base==0)
 86            return false;
 87        $num--;
 88        $ord = $num==0 ? 0 : floor(log($num,$base));
 89        while($ord>0){
 90            $q = pow($base,$ord-1);
 91            $num -= floor($num/pow($base,$ord--))*$q;
 92        }
 93        return $num;
 94    }

La funzione base2no0() mappa i numeri naturali (0, 1, 2…) trasponendoli su numeri senza zeri:

for($i=0; $i<1000; $i++) echo base2no0($i)."\n";

questo codice stamperà 1 2 3 .. 8 9 11 12 .. 19 21 .. 98 99 111 .. cioè i primi 1000 numeri senza zeri. La funzione no0tobase() fa la codifica opposta e restituisce false se si tenta di codificare un numero che contiene zeri (in base n-esima un numero contiene almeno uno zero se è divisibile per n).

Secondo passo: mappare i numeri su stringhe.

 56    function int2alpha($num = 0){
 57        $num = base2no0($num, 27);
 58        $num = base_convert($num, 10, 27).'';
 59        for($i=0; $i<strlen($num); $i++)
 60            $num[$i] = chr(ord('a')+base_convert($num[$i], 27, 10)-1);
 61        return $num;
 62    }
 63
 64    function alpha2int($num = 'a'){
 65        for($i=0; $i<strlen($num); $i++)
 66            $num[$i] = base_convert(ord($num[$i])-ord('a')+1, 10, 27);
 67        $num = base_convert($num, 27, 10);
 68        $num = no0tobase($num, 27);
 69        return $num;
 70    }

La funzione int2alpha() trasforma i numeri filtrati da base2no0() in stringhe, secondo la codifica 1-26. Usa la funzione base_convert() per convertire un numero da base 10 a base 27 (”cifre” da 0 a 26, anche se lo 0 non è rappresentato).

for($i=0; $i<1000; $i++) echo int2alpha($i)."\n";

questo codice stamperà le prime 1000 stringhe in ordine alfabetico: a b c .. x y z aa ab ac .. az ba bb .. bz ca .. zy zz aaa aab aac ..
La funzione alpha2int() è duale rispetto a int2alpha(), restituisce il numero corrispondente alla parola passata come parametro.

Ultimo passo: scrivere la funzione per generare stringhe casuali.
La funzione alpha_rand() (righe 3-46 del codice) accetta quattro parametri:
$min e $max: sono di un certo tipo a seconda degli altri parametri;
$type: i valori possibili sono 'alpha_only' e 'alphanum';
$method: i valori possibili sono 'length', 'alpha_range' (o semplicemente 'range') e 'int_range'.
Come la rand(), anche la alpha_rand() può pescare fino a un valore massimo: getalpharandmax() restituisce tale valore, cioè la stringa che è mappata (almeno su Altervista) sul numero 743925597765 (tale numero è stato calcolato in modo empirico, ho verificato che i numeri successivi danno stringhe sballate e ambigue). getrandmaxlength() dà la lunghezza di tale stringa (9).

 19        if($type != 'alpha_only' && $type != 'alphanum')
 20            return false;
 21        if($method == 'length'){
 22            $length = min(rand($min, $max), getrandmaxlength());
 23            $randmin = $randmax = '';
 24            for($i=0; $i<$length; $i++)
 25                $randmin .= 'a';
 26            for($i=0; $i<$length; $i++)
 27                $randmax .= 'z';
 28            return alpha_rand(alpha2int($randmin), alpha2int($randmax), $type, 'int_range');
 29        }
 30        if($method == 'range' || $method == 'alpha_range')
 31            return alpha_rand(alpha2int($min), alpha2int($max), $type, 'int_range');
 32        if($method != 'int_range')
 33            return false;

In questo pezzo di codice c’è la validazione e il filtraggio dei parametri: tutti i metodi vengono ricondotti al metodo 'int_range' (righe 28 e 31).

 35        $alpha_rand = int2alpha(extended_rand($min, $max));

Questa è la riga principale: trasforma in stringa un numero casuale. Qui uso una extended_rand() (righe 96-105) al posto della rand() perchè arriva fino a 743925597765 anzichè fino a PHP_MAX_INT. La extended_rand() usa la recursive_rand() (righe 107-117) per distribuire meglio la casualità dei numeri.

 37        if($type == 'alphanum'){
 38            $places = range(0, strlen($alpha_rand)-1);
 39            shuffle($places);
 40            $places = array_slice($places, rand(1, strlen($alpha_rand)-1));
 41            foreach($places as $pos)
 42                $alpha_rand[$pos] = rand(0, 9);
 43        }

C’è anche la possibilità di generare una stringa alfanumerica ($type = 'alphanum'). Ho aggiunto questa modalità per completezza, visto che non è una parte fondamentale di questo articolo; per comodità ho semplicemente sostituito alcuni caratteri della stringa letterale con alcune cifre. (Nota: Le stringhe alfanumeriche così generate non sono trasformabili attraverso alpha2int().)

  5        if(func_num_args() == 0)
  6            return alpha_rand('a', getalpharandmax(), 'alpha_only', 'range');
  7        if(preg_match("/[0-9]/", $min) && (!isset($max) || preg_match("/[a-z]/", $max))){
  8            if(func_num_args() > 3)
  9                return false;
 10            if(func_num_args() == 3 && func_get_arg(2) != 'length')
 11                return false;
 12            if(func_num_args() == 2)
 13                $type = func_get_arg(1);
 14            else
 15                $type = 'alpha_only';
 16            return alpha_rand($min, $min, $type);
 17        }

Queste righe sono una comodità per poter passare 3 parametri o nessuno anzichè 4 (vedi esempi 1 e 4).

Esempi
Ecco alcuni esempi di utilizzo (output):

echo alpha_rand();
echo alpha_rand(4, 6);
echo alpha_rand(4, 6, 'alphanum');
echo alpha_rand(3, 'alpha_only', 'length');
echo alpha_rand(3);
echo alpha_rand(703, 731, 'alpha_only', 'int_range');
echo alpha_rand('aab', 'abd', 'alpha_only', 'alpha_range');
echo alpha_rand(alpha2int('aab'), alpha2int('abd'), 'alpha_only', 'int_range');

Riga 1: Nessun parametro -> Stringa letterale qualsiasi tra ‘a’ e il valore di getalpharandmax().
Riga 2: Restituisce una stringa letterale di lunghezza compresa tra 4 e 6 (type = alpha_only, method = length).
Riga 3: Come la 2, tranne che la stringa è alfanumerica.
Riga 4: Forma compatta per alpha_rand(3, 3, 'alpha_only', 'length').
Riga 5: Come la 4.
Righe 6-8: Tutte e tre danno una stringa casuale tra ‘aab’ e ‘abd’ (’aab’, ‘aac’..’aaz’, ‘aba’, ‘abb’, abc’, ‘abd’) (703 -> ‘aab’, 731 -> ‘abd’).

In molti linguaggi di programmazione esistono funzioni che generano un numero casuale. In questo articolo mostrerò come generare invece in modo casuale una stringa. Un modo banale è il seguente:

function alpha_rand($minlength, $maxlength){
    
    $length = rand($minlength, $maxlength);

    $alpha_rand = '';
    for($i=0; $i<$length; $i++)
        $alpha_rand .= chr(ord('a') + rand(0,25));
    
    return $alpha_rand;
}

…ma visto che qui si parla di “scripting avanzato” il codice sarà un po’ più complesso di questo (ovviamente farà anche di più).

Facciamo prima un’analisi di tipo teorico.
Vogliamo generare una stringa in modo simile alla funzione rand() del PHP, ovvero dobbiamo poter dire un valore minimo e un valore massimo tra i quali pescare.
Per facilitarci, vogliamo poter associare una stringa a un numero, ovvero 0 -> a, 1 -> b .. 25 -> z, 26 -> aa, 27 -> ab .. in modo da poter scrivere:

$stringa = alpha_rand(10, 24);
$stringa = alpha_rand(26, 51);

nel primo caso darà una lettera casuale tra ‘k’ (l’11ª, il conteggio parte da 0) e ‘y’ (la 25ª), nel secondo caso darà una parola tra ‘aa’ e ‘az’ (’aa’, ‘ab’, ‘ac’..’ay’, ‘az’).

Vediamo quindi in che modo possiamo convertire una stringa in un numero. Un modo facile è trasformare ogni singola cifra in una lettera; proviamo ad associare le lettere ai numeri da 0 a 25:
0 -> a, 1 -> b, 2 -> c .. 25 -> z
C’è però un problema. I numeri da 0 a 25 vengono trasformati correttamente, ma prendiamo il 26: il ‘26′ in base 26 si scrive ‘10′ (cambiamenti di base: funzione base_convert()), che diventerebbe ‘ba’ secondo la codifica ipotizzata poco fa (27 -> 11 -> ‘bb’, 28 -> 12 -> ‘bc’ .. 676 -> 100 -> ‘baa’ ..). In questa codifica mancano tutte le stringhe che iniziano per ‘a’ (’aa’ -> ‘00′, ‘ab’ -> ‘01′, ‘aac’ -> ‘002′, ma sarebbero uguali a 0, 1 e 2, già trasformati in ‘a’, ‘b’ e ‘c’).

Proviamo in un altro modo. Stavolta associamo alle lettere i numeri da 1 a 26:
1 -> a, 2 -> b, 3 -> c .. 26 -> z
C’è un problema palese: lo 0 non ha codifica! Però stavolta non ci sono codifiche ambigue.
Questa è la codifica che useremo nello script.

Continua…

Ecco il secondo script di questo blog. Questo, assieme al primo, è utile per la creazione veloce di file.
Lo script contiene due funzioni: newfilename() e backup().

function newfilename($path, $subst = "_new", $insert = true, $check = false){
    if(!$insert){
        if($check && file_exists($path . $subst))
            return false;
        return $path . $subst;
    }
    $filename = basename($path);
    $pos = strrpos($filename, '.');
    if($pos !== false){
        $fileext = substr($filename, $pos);
        $filename = substr($filename, 0, $pos);
    }else
        $fileext = '';
    $pos = strrpos($path, '/');
    $dir = $pos === false ? '' : substr($path, 0, $pos+1);
    $newfilename = $dir . $filename . $subst;
    if($check && file_exists($newfilename . $fileext))
        return false;
    return $newfilename . $fileext;
}

La funzione newfilename() accetta quattro parametri:
$path: il percorso di un file;
$subst: una stringa;
$insert e $check: variabili booleane.
Tale funzione prende il nome del file contenuto nel $path e ci aggiunge la stringa $subst: se $insert è false lo aggiunge alla fine ({nomefile}[{estensione}]{stringa}), sennò lo aggiunge tra l’estensione e il nome del file ({nomefile}{stringa}[{estensione}]). Se la variabile $check è true, la funzione verifica se il nome di file appena generato corrisponde a un file già esistente: in tal caso la funzione restituisce false; se $check è false non fa questo controllo. Di default, la funzione inserisce la stringa “_new” in mezzo e non fa nessun controllo sull’esistenza del file.

function backup($path, $subst = "_bak", $insert = false, $check = true){
    $subst_w = $subst;
    while(($backup = newfilename($path, $subst_w, $insert, $check)) === false)
        $subst_w .= $subst;
    return $backup;
}

La funzione backup() non esegue il backup vero e proprio di un file ma trova solo un nome da usare. Funziona esattamente come newfilename(), ma di default inserisce la stringa “_bak” alla fine del nome e controlla se il file (backup) esiste già, in tal modo non sovrascrive i backup precedenti. Nel ciclo while verifica con la newfilename() se il nuovo backup esiste già: continua ad aggiungere la stringa alla fine finchè non trova un nome non ancora usato.

Le funzioni newfile() e newfname() sono due alias di newfilename()

Ecco uno script di esempio (qui viene fatto backup dell’ultimo file creato).

Cominciamo con qualcosa di semplice: le seguenti funzioni manipolano (lettura/scrittura) un generico file in modo facile e breve.

<?php

function filewrite($filename, $content = '', $mode = 'w'){

    $fp = fopen($filename, $mode);
    fwrite($fp, $content);
    fclose($fp);

}

function fileappend($filename, $content = ''){

    filewrite($filename, $content, 'a');

}

function filecreate($filename){

    filewrite($filename);

}

function filedelete($filename){

    unlink($filename);

}

function fileread($filename, $offset = 0, $length){

    $fp = fopen($filename, 'r');
    if($offset < 0)
        $offset = filesize($filename)+$offset;
    $offset = min($offset, filesize($filename));
    if(!isset($length))
        $length = filesize($filename)-$offset;
    elseif($length < 0)
        $length = filesize($filename)-$offset+$length;
    else
        $length = min($length, filesize($filename)-$offset);
    if($length == 0)
        $content = '';
    else{
        fseek($fp, $offset);
        $content = fread($fp, $length);
    }
    fclose($fp);
    return $content;
}

function fileinsert($filename, $content, $pos = 0){

    $fp = fopen($filename, 'r+');
    if(is_array($pos))
        for($i=0; $i<count($pos); $i++){
            fseek($fp, $pos[$i]);
            if(is_array($content))
                fwrite($fp, $content[$i]);
            else
                fwrite($fp, $content);
        }
    else{
        fseek($fp, $pos);
        if(is_array($content))
            $content = implode('',$content);
        fwrite($fp, $content);
    }
    fclose($fp);

}

?>

Analizziamo il codice:
filewrite()
scrive il $content dentro il file $filename; la modalità predefinita è 'w', quindi se il file esiste già lo sovrascrive;
fileappend()
come filewrite() ma usa la modalità 'a', quindi il $content viene aggiunto alla fine del file; il file viene creato se non esiste;
filecreate()
crea un file vuoto;
filedelete()
alias di unlink();

fileread()
si comporta esattamente come substr() salvo il fatto che si applica direttamente al file. Nel codice si nota che “traduco” i valori negativi di $offset e $length per ricondurmi al caso di valori solo positivi (per es. su un file di 100 byte, -25 corrisponde a 75). In caso di errore (offset maggiore della lunghezza del file, numero di byte letti che sfora la fine del file), la funzione restituisce una stringa vuota;

fileinsert()
modifica alcuni byte all’interno del file; utilizza la fopen() in modalità 'r+', che permette di scrivere sul file senza cancellarne il contenuto. Questa funzione è utile nel caso di file con formato.
Alla funzione passo i parametri $content e $pos: entrambi possono essere o un dato singolo o un vettore di dati. Ho creato uno script di esempio per far capire meglio come funziona (viene mostrato anche il codice usato): in questo caso ogni dato è formato da 5 cifre.

Algoritmo: Sequenza finita di istruzioni, descritta in maniera chiara e non ambigua
Programma: Formalizzazione di un algoritmo per mezzo di un linguaggio di programmazione
Processo: Programma in esecuzione su un insieme di dati, elaborati in modo deterministico

Questo blog nasce per illustrare alcuni script più o meno utili ai programmatori, parte dei quali sono scritti o riarrangiati da me. Gli algoritmi e i relativi codici utilizzati saranno spiegati nei dettagli. Il livello di difficoltà degli script sarà medio-elevato; si consiglia ai principianti di leggere le guide che ho messo a destra.
Il blog ha anche l’intento di portare il lettore (presunto programmatore) nell’ottica di poter risolvere problemi più o meno complessi, e di indurlo a usare algoritmi intuibili facili da implementare.
Disclaimer: I codici illustrati sono ovviamente visibili (e copiabili) da chiunque, ma ciò non significa che non dobbiate avere la cortezza di fare un riferimento esplicito a questo blog qualora li pubblicaste in qualche altro sito o forum o blog!

La maggior parte degli script che illustrerò sarà in PHP, alcuni useranno anche il Javascript, una parte anche il C ma in verità probabilmente farò solo qualche accenno a questo linguaggio, o al più metterò degli script che ho fatto sia in C sia in PHP.

Tutti i codici (più eventuali esempi) si trovano anche in una directory su uno dei miei siti; il link lo trovate sulla destra del blog, dove leggete “Tutti i codici“.

Cosa c’è e cosa manca in questo blog: Gli script sono fatti per girare sicuramente sul circuito di Altervista.org (il quale ospita anche questo blog), ma possono essere eventualmente adattati per qualunque dominio.
Scriverò articoli su ciò che conosco meglio: PHP4 e database testuali, non vedrete MySQL o altri linguaggi specifici per i database.

Per mostrare il codice userò questo tag:

<?php
    echo "ciao!";
?>

Ove possibile eviterò l’uso delle graffe, userò invece sempre l’indentazione.

Buona lettura! e non dimenticate di commentare!