Io e l'Integer Packing come funziona il pack e unpack di interi in C

Annie: Oh, vai dallo psichiatra?
Alvy: S-sì. Da quindici anni soli...
Annie: Quindici anni?!
Alvy: Sì... gli concedo un altro anno... poi vado a Lourdes.

Nel capolavoro Io e Annie il Maestro Woody Allen ci proponeva, attraverso una personalissima "commedia romantica nevrotica", l'analisi della relazione tra i protagonisti Alvy Singer e Annie Hall in tutte le sue fasi (l'inizio/la relazione/la fine), mettendo in mostra fatti e misfatti in cui tutti ci possiamo riconoscere. Allo stesso modo (ma non con la classe del Maestro, purtroppo) cercherò con questo articolo di ricreare e (spero) risolvere una situazione che tutti i programmatori che si sporcano le mani con la programmazione low-level hanno dovuto affrontare (...ebbene si, cari programmatori high-level: sotto le vostre splendide applicazioni gira sempre del Software low-level, quasi sempre scritto in C, non dimenticatevelo...).

...Alvy: il pack/unpack di interi... Annie: argomento interessantissimo (yawn)...

Supponiamo (ma proprio supponiamo) che abbiamo due interi da 16 bit che vogliamo, magicamente, trasformare in un unico intero da 32 bit. Oppure vogliamo fare l'operazione inversa (spezzare un int a 32 bit in due int a 16 bit). Oppure abbiamo quattro interi da 16 bit e vogliamo... blah, blah, bla. I casi appena descritti non sono fantascienza, anzi sono casi abbastanza normali: ad esempio chi maneggia giornalmente i registri di periferiche Modbus sicuramente si è trovato a dover fare operazioni di questo tipo. Ecco, chi usa queste operazioni frequentemente può anche saltare il resto dell'articolo (e magari usare il tempo risparmiato per guardarsi un buon film e alimentare così la propria mente).

Ma, visto che mi è capitato di vedere facce terrorizzate di fronte a problemoni come questo (specialmente tra i colleghi non avvezzi alla programmazione low-level), cercherò di proporre alcune soluzioni, dopodiché si noterà che il tutto è di una semplicità disarmante. Si può, ovviamente, risolvere in 33 (o 33000) modi diversi, io ho pensato di mostrare i 3 modi che mi sembrano più semplici, lineari ed efficienti. Gli esempi che seguono sono di pack e unpack di interi a 32 bit (2 registri da 16bit in un intero da 32 bit e viceversa), ma adattare gli esempi ai 64 bit (4 registri da 16bit in un intero da 64 bit e viceversa) è veramente un gioco da ragazzi, e quindi non ve lo mostro nemmeno. Vai col codice dell'esempio 1!:

1) pack32 e unpack32 con bitwise

// pack32bitwise - copia un array di 2 uint16_t dentro una variabile uint32_t
uint32_t pack32bitwise(
    const uint16_t *src)    // array sorgente per il pack
{
    // ottiene il valore destinazione dal valore sorgente
    return ((uint32_t)src[1]) << 16 | src[0];
}

// unpack32bitwise - copia una variabile uint32_t in un array di 2 uint16_t
uint16_t *unpack32bitwise(
    uint16_t       *dest,   // array destinazione
    const uint32_t src)     // valore sorgente per l'unpack
{
    // ottiene il valore destinazione dal valore sorgente
    dest[1] = (uint16_t)((src & 0xFFFF0000) >> 16);
    dest[0] = (uint16_t)( src & 0x0000FFFF);

    return dest;
}

Questo è il modo più semplice e (probabilmente) più efficiente per fare il pack/unpack (io di solito uso questo). Si effettuano delle semplici operazioni di bitwise, che spostano o copiano i valori di entrata sull'uscita. Ovviamente la funzione pack() si aspetta un array come argomento e restituisce il valore intero corrispondente. Specularmente la funzione unpack() si aspetta un argomento con un valore e un argomento destinazione che sarà un array. Le operazioni di bitwise sono semplicissime: usando lo shift a 16 (visto che usiamo interi a 16 bit) possiamo copiare/spostare/mascherare opportunamente per ottenere il risultato voluto. Ed ora siamo pronti per l'esempio 2. vai col codice!:

2) pack e unpack con union

// pack32union - copia un array di 2 uint16_t dentro una variabile uint32_t
uint32_t pack32union(
    const uint16_t *src)    // array sorgente per il pack
{
    union {
        uint16_t src[2];
        uint32_t dest;
    } u;

    // ottiene il valore destinazione dal valore sorgente
    u.src[0] = src[0];
    u.src[1] = src[1];

    return u.dest;
}

// unpack32union - copia una variabile uint32_t in un array di 2 uint16_t
uint16_t *unpack32union(
    uint16_t       *dest,   // array destinazione
    const uint32_t src)     // valore sorgente per l'unpack
{
    union {
        uint16_t dest[2];
        uint32_t src;
    } u;

    // ottiene il valore destinazione dal valore sorgente
    u.src = src;
    dest[0] = u.dest[0];
    dest[1] = u.dest[1];

    return dest;
}

Questa maniera per eseguire il pack/unpack è quasi un trucco: si sfrutta una particolarità del linguaggio (il funzionamento delle union) in maniera impropria (non è che le union servono esattamente a quello)... ma visto che funziona perché non farlo? Quindi basta creare una union della forma opportuna e, assegnato a un membro della union il valore in ingresso, troveremo nell'altro membro della union il valore "rimappato" di uscita, esattamente quello che ci serve, no? Per chi in questo momento ha un vuoto di memoria su come funzionano le union basta ricordarsi di questo: la dimensione di una union è quella di un membro solo (quello che occupa più memoria) e, nel nostro caso, visto che i due membri occupano lo stesso spazio ma sono di tipo diverso ci viene offerto un immediato recasting implicito. Semplicissimo! Ed ora passiamo all'ultimo esempio. vai col codice!:

3) pack e unpack con memcpy()

// pack32memcpy - copia un array di 2 uint16_t dentro una variabile uint32_t
uint32_t pack32memcpy(
    const uint16_t *src)    // array sorgente per il pack
{
    // copia il valore sorgente nella destinazione
    uint32_t dest;
    memcpy(&dest, src, sizeof(dest));

    return dest;
}

// unpack32memcpy - copia una variabile uint32_t in un array di 2 uint16_t
uint16_t *unpack32memcpy(
    uint16_t       *dest,   // array destinazione
    const uint32_t src)     // valore sorgente per l'unpack
{
    // copia il valore sorgente nella destinazione
    uint32_t mysrc = src;
    memcpy(dest, &mysrc, sizeof(mysrc));

    return dest;
}

Visto che le operazioni di pack/unpack sono, bene o male, operazioni di copia/spostamento di memoria, non poteva mancare un esempio con la memcpy(), che è l'oggetto privilegiato e preferito quando si parla di operazioni di questo tipo. Mi risulta che questo metodo è molto usato, e l'ho usato anch'io ma, ultimamente, uso più spesso il metodo 1 (anche perché col metodo 1 è facilissimo, nel caso risulti necessario, invertire l'ordine dei registri. Non è usuale ma a volte capita). Il codice è così semplice che non c'è quasi nulla da spiegare: sfruttando il fatto che la memcpy() usa argomenti di tipo void* è perfettamente usabile per una operazione come la nostra, che consiste, a tutti gli effetti, nella copia di un blocco di memoria di un tipo in uno di un tipo diverso. A questo punto cosa ci manca? ma un bell'esempio d'uso, chiaro! Eccolo:

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

// prototipi locali
uint32_t pack32bitwise(const uint16_t *src);
uint16_t *unpack32bitwise(uint16_t *dest, const uint32_t src);
uint32_t pack32union(const uint16_t *src);
uint16_t *unpack32union(uint16_t *dest, const uint32_t src);
uint32_t pack32memcpy(const uint16_t *src);
uint16_t *unpack32memcpy(uint16_t *dest, const uint32_t src);

// funzione main
int main(int argc, char *argv[])
{
    // set variabili per test pack32()
    uint16_t src1[2];
    uint32_t dest1;
    src1[0] = 10;
    src1[1] = 20;

    // test pack32()
    dest1 = pack32bitwise(src1);;
    printf("con bitwise: src1={%d,%d} dest1=%d\n", src1[0], src1[1], dest1);
    dest1 = pack32union(src1);;
    printf("con union:   src1={%d,%d} dest1=%d\n", src1[0], src1[1], dest1);
    dest1 = pack32memcpy(src1);;
    printf("con memcpy:  src1={%d,%d} dest1=%d\n", src1[0], src1[1], dest1);

    // set variabili per test unpack32()
    uint32_t src2 = 1310730;
    uint16_t dest2[2];

    // test unpack32()
    unpack32bitwise(dest2, src2);
    printf("con bitwise; src=%d dest={%d,%d}\n", src2, dest2[0], dest2[1]);
    unpack32union(dest2, src2);
    printf("con union:   src=%d dest={%d,%d}\n", src2, dest2[0], dest2[1]);
    unpack32memcpy(dest2, src2);
    printf("con memcpy:  src=%d dest={%d,%d}\n", src2, dest2[0], dest2[1]);

    return 0;
}

Ecco, con questo piccolo main() di esempio potrete verificare che le varie versioni di pack e unpack offrono sempre gli stessi risultati (e ci mancherebbe solo che non fosse così!). E con questo ho detto tutto, e vi lascio, come compiti delle vacanze (vacanze? quali vacanze?) la trasformazione di tutti gli esempi a 32 bit in esempi a 64 bit: come ho già detto più sopra, è un gioco da ragazzi!

Ciao e al prossimo post!

Buone Feste!

I Misteri delle Funzioni del C come funzionano alcune funzioni speciali in C - pt.2

Sig.ra Talmann: Il tuo discorso, Louis, sta diventando meteorologico.

È giunto il momento di tornare su I misteri del giardino di Compton House, anzi meglio, sulla seconda parte de I Misteri delle Funzioni del C (...e una ripassatina alla prima parte non ci starebbe male, prima di proseguire...). E giuro che cercherò di non cadere in discorsi meteorologici e incomprensibili come Louis Talmann.

...misteri? Quali misteri?...

(...una doverosa premessa: sicuramente per qualcuno, o per molti, i misteri trattati nella prima parte e, probabilmente, anche questi della seconda non sono affatto misteri. Ma voglio ribadire quanto già detto nella prima parte: girando su vari siti di programmazione (tipo l'ottimo stackoverflow, per intenderci), si nota che anche programmatori "scafati" hanno, a volte, dubbi su concetti di base (e chi non ne ha mai avuti scagli la prima pietra!) e poi, più in generale, la lettura di "un altra campana tecnica" può risultare sempre interessante, dando per scontato che la "curiosità tecnologica" è una dote che dovrebbe (anzi, deve!) essere sempre presente negli appassionati di programmazione. Che poi, se uno questa curiosità non ce l'ha... va beh, meglio fermarsi qui, No Comment...) 

Veniamo al dunque: dopo aver visto i primi tre misteri e cioè 1.Il mistero delle funzioni con un parametro array, 2.Il mistero delle funzioni che restituiscono una stringa letterale e 3.Il mistero delle funzioni che restituiscono un char pointer direi che il quarto mistero è quasi scontato, ed è:

4) Il mistero delle funzioni che restituiscono un void pointer
Nella libc ci sono un bel po' di funzioni che restituiscono un void* (per gli amici "void star"), come ad esempio quelle delle famiglia mem (memcpy(), memccpy(), ecc.). Come sono fatte? Ci sono alternative valide alla struttura "classica"? Vediamo un semplice esempio con una implementazione minimale della memcpy(), senza controlli, senza ottimizzazioni, senza tutto, ma per un esempio è più che sufficiente. Vediamo il codice, che anche in questo caso include un piccolo e semplice main() di test:

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

// prototipi locali
void *myMemcpy(void *dest, const void *src, size_t len);
void *myMemcpyMalloc(void *dest, const void *src, size_t len);

// funzione main
int main(int argc, char *argv[])
{
    // eseguo myMemcpy() e mostro il risultato
    char *src1 = "pluto";
    char dest1[32];
    myMemcpy(dest1, src1, strlen(src1) + 1);
    dest1[strlen(src1)] = 0;    // ricordarsi del terminatore se copiamo una stringa
    printf("myMemcpy(): dest = %s\n", dest1);

    // eseguo myMemcpyMalloc() e mostro il risultato
    char *src2 = "minnie";
    char *dest2 = myMemcpyMalloc(dest2, src2, strlen(src2) + 1);
    dest2[strlen(src2)] = 0;    // ricordarsi del terminatore se copiamo una stringa
    printf("myMemcpyMalloc(): dest = %s\n", dest2);
    free(dest2);                // ricordarsi di questa free()

    return 0;
}

// myMemcpy - versione semplificata della memcpy() della libc
void *myMemcpy(void *dest, const void *src, size_t len)
{
    // salvo localmente dest e src ed eseguo un recast a char*
    char *my_dest = (char *)dest;
    const char *my_src  = (const char *)src;

    // copio la copia locale di src sulla copia locale di dest (copio solo <len> caratteri)
    while (len--)
        *my_dest++ = *my_src++;

    // ritorno il dest salvato
    return dest;
}

// myMemcpyMalloc - versione con malloc interna di myMemcpy()
void *myMemcpyMalloc(void *dest, const void *src, size_t len)
{
    // alloco dest (N.B.: la free() la deve fare il chiamante della myMemcpyMalloc())
    dest = malloc(len);

    // salvo localmente dest e src ed eseguo un recast a char*
    char *my_dest = (char *)dest;
    const char *my_src  = (const char *)src;

    // copio la copia locale di src sulla copia locale di dest (copio solo <len> caratteri)
    while (len--)
        *my_dest++ = *my_src++;

    // ritorno il dest salvato
    return dest;
}

Anche in questo caso il meccanismo è semplice e quasi identico a quello della strncpy() mostrato nella parte 1 dell'articolo. Senza entrare di nuovo nei dettagli (per non ripeterci, e poi il codice è ben commentato), notiamo che la unica differenza vera è che la copia viene eseguita usando copie locali di src e dest "ricastate" a char: perché? La riposta è semplice: questo tipo di funzioni accettano parametri generici (grazie all'uso di void*), quindi si possono passare pointer a strutture, array, ecc. Ma poi, internamente, la copia si fa byte-a-byte, per cui si riconduce tutto al (magico) tipo char*. E, ovviamente, si ritorna sempre l'argomento dest originale, per i motivi già descritti sopra. E anche in questo caso ho pensato di aggiungere una memcpy() poco canonica, con allocazione interna, per la quale valgono tutte le considerazione fatte per la myStrncpyMalloc() già descritta.

Notare che, per coerenza con gli esempi della prima parte del post (e anche per mostrare con semplicità un risultato pratico) ho usato le due myMemcpy() per copiare una stringa (non è un uso classico, ma chi lo vieta?). Ovviamente ho provveduto, a livello main(), ad aggiungere un string terminator, visto che la myMemcpy() a differenza della myStrncpy() già vista, non può (anzi, non deve) pensare a eventuali terminatori di stringa già che è una funzione generica di copia di memoria.

E adesso possiamo cambiare un po' argomento (basta con 'ste funzioni di copia!) e possiamo passare, per esempio a:

5) il mistero delle funzioni con vettori di pointer
Come possiamo generare e maneggiare un vettore di pointer (o meglio: pointer-to-pointers, per gli amici star-star) usando funzioni? Vediamo un esempio semplice semplice, con il solito main() per mostrare i risultati:

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

#define N_ELEMS 3   // numero di elementi da allocare nel vettore

// una semplice struttura di dati
typedef struct {
    int  id;
    char name[32];
} s_data;

// prototipi locali
s_data **allocVect(s_data **dest, size_t n_elems);
void   freeVect(s_data **dest, size_t n_elems);

// funzione main
int main(int argc, char *argv[])
{
    // alloco il vettore per il test
    s_data **datalist = allocVect(datalist, N_ELEMS);

    // scorro il vettore e mostro il contenuto
    for (int i = 0; i < N_ELEMS; i++)
        printf("allocVect(): datalist[%d]: id=%d name=%s\n",
               i, datalist[i]->id, datalist[i]->name);

    // libero il vettore
    freeVect(datalist, N_ELEMS);

    return 0;
}

// allocVect - alloca un vettore di pointer
s_data **allocVect(s_data **dest, size_t n_elems)
{
    // alloco il pointer-to-pointers
    dest = malloc(n_elems * sizeof(s_data));

    // alloco i pointer
    for (int i = 0; i < n_elems; i++) {
        dest[i] = malloc(sizeof(s_data));

        // questa parte è solo un esempio per mettere dei dati da mostrare nel main()
        dest[i]->id = i;
        snprintf(dest[i]->name, sizeof(dest[i]->name), "name_%d", i);
    }

    // ritorna il pointer-to-pointers
    return dest;
}

// freeVect - libera un vettore di pointer
void freeVect(s_data **dest, size_t n_elems)
{
    // scorro il vettore e libero ogni pointer
    for (int i = 0; i < n_elems; i++)
        free(dest[i]);

    // libera il pointer-to-pointers
    free(dest);
}

Avete visto? Ho scritto due semplicissime funzioni per allocare e liberare un vettore di puntatori (star-star), e la chiave del funzionamento (ben commentata, direi) è la seguente: quando abbiamo un vettore di pointer bisogna creare prima il pointer-to-pointers base (con malloc()) e poi bisogna creare i singoli puntatori del vettore (sempre con malloc()). E quando si libera il vettore bisogna, ovviamente, seguire l'ordine inverso (prima i puntatori singoli e poi il pointer-to-pointers principale). nell'esempio appena mostrato ho aggiunto nel loop di creazione una inserzione di dati, per avere qualcosa da mostrare nel main(): compilatelo, vi assicuro che funziona...

Notare che in questo caso il meccanismo di passaggio e uso degli argomenti è quello visto negli esempi "non canonici" visti nei precedenti misteri: si passa un argomento spurio (un dest non allocato) e lo si restituisce allocato al chiamante. Semplice, no?

E dopo questo esempio credo che siamo pronti per l'ultimo mistero di questa seconda e (per il momento) ultima parte dell'articolo:

6) il mistero delle funzioni per maneggiare linked-list
Le linked-list sono uno dei grandi misteri del C, eppure sono utilissime, e sono anche molto semplici da usare! Vediamo un esempio veramente elementare:

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

#define N_NODES 3   // numero di nodi nella linked list

// nodo di una linked list singola con campo dati
typedef struct snode {
    int data;
    struct snode *next;
} node_t;

// prototipi locali
void addNode(node_t **head, int data);

// funzione main
int main(int argc, char *argv[])
{
    // init lista vuota e inserisce con addNode() N_NODES nodi con data = indice loop
    node_t *head = NULL;
    for (int i = 1; i <= N_NODES; i++)
        addNode(&head, i);

    // scorre la lista e stampa i valori (compresi gli indirizzi)
    node_t *my_head = head;
    printf("my_head=%p\n", my_head);
    while (my_head) {
        printf("data=%d (my_head=%p next=%p)\n", my_head->data, my_head, my_head->next);
        my_head = my_head->next ;
    }

    return 0;
}

// addNode - alloca in testa a una lista un node con dati e puntatore al prossimo elemento
void addNode(node_t **head, int data)
{
    // alloca un nuovo node
    node_t *node = malloc(sizeof(node_t));
    node->data = data;
    node->next = *head;

    // assegna head lista al nuovo node
    *head = node;
}

Cosa dire? più elementare di così! Eppure funziona... Come si evince dagli abbondanti commenti per fare una linked-list basta creare un punto di inizio (un "head") e aggiungere nodi con una semplicissima funzione che ho chiamato (in modo veramente originale) addNode(). Il segreto sta nella struttura del "nodo", che deve sempre contenere un puntatore al nodo successivo (ma va? Sarà mica per questo che si chiamano linked-list?). Ovviamente l'esempio fornito è abbastanza limitato, e mancano le funzioni per cancellare nodi, per appendere (invece di aggiungere) nodi, oppure per gestire la lista in modo doppio (double-linked-list), ecc., ecc. Ma sulla (solida) base fornita è possibile costruire, in modo relativamente semplice, tutte le estensioni che vogliamo.

Una ultima cosa: notare che il main() mostra, a titolo di esempio, il campo data dei nodi aggiunti insieme agli indirizzi del nodo corrente e del prossimo, e questo ci aiuta a vedere in pratica come funziona il meccanismo.

Beh, direi che con i tre misteri di oggi abbiamo svelato ulteriori dettagli arcani delle funzioni C. Ne rimangono ancora molti, ma per il momento ci prenderemo una pausa, perché sento già friggere molti neuroni e non vorrei creare danni irreversibili...

Ciao e al prossimo post!