Lettura di una bitmap

Le immagini bitmap, introdotte nel 1990 con Windows 3.0, organizzano le informazioni all'interno di più strutture dati. Il file inizia con la struttura dati BITMAPFILEHEADER, di 14 byte. All'interno di questa prendono posto alcune importanti informazioni come la dimensione in byte del file, lo scostamento del primo pixel dell'immagine a partire dall'inizio del file e una stringa in ascii con il valore BM (valore decimale 19778, esadecimale 4D42). La successiva struttura dati, BITMAPINFOHEADER, di 40 byte, raccoglie invece altre informazioni, come ad esempio: le dimensioni in pixel dell'immagine, il numero di byte usato per ogni pixel, la risoluzione orizzontale e verticale etc... Qui trovate una descrizione dettagliata delle informazioni che è possibile rintracciare negli header di un file bmp. L'ultima struttura dati è infine la mappa dei pixel: ad ogni pixel corrisponde un colore sotto forma di codice (o indice se l'immagine usa una tavolozza di colori). Ogni codice specifica le componenti cromatiche dei colori primari (rosso, verde e blu) miscelati per ottenere il colore assegnato al pixel!
Possiamo leggere e scrivere queste informazioni (sia gli header che la mappa dei pixel) aprendo il file in modalità binaria e leggendo con fread n byte alla volta, a seconda della struttura dati. E' possibile assegnare i byte letti con fread a delle variabili (header1 e header2) e usare queste informazioni all'interno di un programma. Nel codice che propongo, dopo aver letto le informazioni (utili tra l'altro ad allocare in memoria un array di n char, uno per ogni pixel) eseguo prima con fseek il riposizionamento del puntatore all'inizio della mappa dei pixel (usando lo scostamento rimediato con la variabile header1), successivamente eseguo la lettura dei pixel. Il programma termina con la stampa della mappa dei pixel ma può essere esteso ulteriormente per l'editing dell'immagine (in tal caso si accederà al pixel con fwrite).

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

#pragma pack(2) // usa 2 byte per impachettare la struttura, che è di 14 byte (non è un multiplo del byte)!
/* BITMAPFILEHEADER (14 byte) */
typedef struct {
   unsigned short int bfType;
   unsigned int bfSize;
   unsigned short int bfReserved1,bfReserved2;
   unsigned int bfOffBits;
} BITMAPFILEHEADER;

#pragma pack()
/* BITMAPINFOHEADER (40 byte) */
typedef struct {
   unsigned int biSize;
   int biWidth;
   int biHeight;
   unsigned short int biBitCount;
   unsigned int biCompression;
   unsigned int biSizeImage;
   int biXPelsPerMeter;
   int biYPelsPerMeter;
   unsigned int biClrUsed;
   unsigned int biClrImportant;
} BITMAPINFOHEADER;

/* struttura per un pixel */
typedef struct {
   unsigned char blue;
   unsigned char green;
   unsigned char red;
} PIXEL;

/* codice (binari e esadecimali) relativi ai file bmp */
#define DECBMPCODE 19778
#define HEXBMPCODE 0x4D42

int main (int argc, char*argv[]) {
   FILE *input_file;
   BITMAPFILEHEADER header1;
   BITMAPINFOHEADER header2;
   PIXEL pixel, *image;
   int i,j,n_pixel=0;

   if (argc==1) {
      printf("Specifica il file da usare!\n");
      return -1;
   }
   else {
      if ((input_file=fopen(argv[1],"rb+"))!=NULL) {
         fread(&header1,sizeof(header1),1,input_file);
         if (header1.bfType==DECBMPCODE) {
            printf("Header del file %s:\n",argv[1]);
            printf(" - Tipo di file: %x\n",header1.bfType);
            printf(" - Dimensione del file: %u Kb (%u byte)\n",header1.bfSize/1024,header1.bfSize);
            printf(" - Offset al primo bit nella mappa: %u\n",header1.bfOffBits);
            fread(&header2,sizeof(header2),1,input_file);
            printf("Header delle informazioni:\n");
            printf(" - Dimensione del blocco informazione: %u byte\n",header2.biSize);
            printf(" - Larghezza dell'immagine: %u pixel\n",header2.biWidth);
            printf(" - Altezza dell'immagine: %u pixel\n",header2.biHeight);

            /* Calcolo del padding */
            int pitch = header2.biWidth * 3;
            if (pitch % 4 != 0) pitch += 4 - (pitch % 4);
            int padding = pitch - (header2.biWidth * 3);
            printf(" - Pitch: %u\n", pitch);
            printf(" - Padding: %u\n", padding);

            fseek(input_file,header1.bfOffBits,SEEK_SET);
            image=(PIXEL*)malloc((header2.biWidth*header2.biHeight)*sizeof(PIXEL));
            printf("\nComponenti dei pixel: #pixel(RGB)\n");
            for (i=0;i<header2.biHeight;i++) {
               for (j=0;j<header2.biWidth;j++) {
                  fread(&pixel, sizeof(PIXEL),1,input_file);
                  printf("%2d(%u,%u,%u) ",n_pixel,pixel.red,pixel.green,pixel.blue);
                  image[n_pixel]=pixel;
                  n_pixel++;
               }
               fseek(input_file, padding, SEEK_CUR);
               printf("\n");
            }
            free(image);
         }
         else {
            printf("Il file %s non è un file bmp!\n",argv[1]);
            return -1;
         }
      }
      else {
         printf("Non è stato possibile aprire il file %s!\n",argv[1]);
         return -1;
      }
   }
   return 0;
}

E' possibile verificare il programma con una delle seguenti immagini:

Il cifrario di Vigenere

Il cifrario di Vigenere applica al testo da codificare la seguente sostituzione: i caratteri che compongono le parole vengono spostati di n posti in virtù di una parola (detta worm, verme) che stabilisce per ognuno di questi lo scostamento. A differenza del cifrario di Cesare che applica ai caratteri della parola sempre lo stesso scostamento (Cesare, ad esempio, spostava in avanti i caratteri di tre posizioni), il cifrario di Vigenere applica ai caratteri uno scostamento variabile! Ad ogni carattere della parola da codificare viene sommato il carattere del verme scelto (che può essere una semplice parola o anche un versetto). Un indice punta sempre al carattere del verme, quando l'indice (che viene incrementato ad ogni somma) giunge all'ultimo carattere del verme viene di nuovo fatto puntare al primo carattere! Tale rotazione deve poi avvenire anche sul carattere codificato. Pertanto, se la somma fra i caratteri (quello del verme e quello della parola in chiaro) sposta il carattere codificato oltre la lettera Z, gli scostamenti riprendono allora dalla lettera A. La decodifica avviene allora sottraendo lo scostamento indicato dal carattere del verme al carattere codificato. Nel programma che propongo l'input e l'output avvengono su file. In fase di codifica il programma chiede il nome di un file da codificare e ne verifica l'esistenza. Viene poi chiesta la parola da usare come verme. L'operazione di codifica produce il file file_codificato.txt. In fase di decodifica viene invece chiesto il file da decodificare, al termine dell'operazione è possibile trovare il file file_decodificato.txt contenente il testo di partenza!


/* cifrario di vigenere */
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAX_LENGTH 1024

int exist(char file_name[MAX_LENGTH]);
void code(char source_file_name[MAX_LENGTH],char worm[MAX_LENGTH]);
void decode(char source_file_name[MAX_LENGTH],char worm[MAX_LENGTH]);

int main(void) {
   int choice,worm_length;
   char worm[MAX_LENGTH];
   char file_name[MAX_LENGTH];
   FILE *source_file;

   do {
      printf("1. codifica;\n");
      printf("2. decodifica;\n");
      printf("Scelta: ");
      scanf("%d",&choice);
   } while (choice!=1 && choice!=2);
   if (choice==1) { /*code */
      getchar();
      printf(" Codifica file:\n");
      printf(" - Seme: ");
      fgets(worm,sizeof(worm),stdin);
      worm[strlen(worm)-1]=0;
      worm_length=strlen(worm);
      printf(" - Lunghezza del seme: %d\n",worm_length);
      printf(" - File sorgente: ");
      fgets(file_name,sizeof(file_name),stdin);
      file_name[strlen(file_name)-1]=0;
      if (exist(file_name)==0) {
         printf("Attenzione: il file %s non esiste!\n",file_name);
         return -1;
      }
      printf(" - Codifica: ");
      code(file_name,worm);
      printf(" completata!\n");
   }
   else if(choice==2) { /* decode */
      getchar();
      printf(" Decodifica file:\n");
      printf(" - Seme: ");
      fgets(worm,sizeof(worm),stdin);
      worm[strlen(worm)-1]=0;
      worm_length=strlen(worm);
      printf(" - Lunghezza del seme: %d\n",worm_length);
      printf(" - File sorgente: ");
      fgets(file_name,sizeof(file_name),stdin);
      file_name[strlen(file_name)-1]=0;
      if (exist(file_name)==0) {
         printf("Attenzione: il file %s non esiste!\n",file_name);
         return -1;
      }
      printf(" - Decodifica: ");
      decode(file_name,worm);
      printf(" completata!\n");
   }
   return 0;
}

/* verifica l'esistenza di un file, 1 altrimenti 0 */
int exist(char file_name[MAX_LENGTH]) {
   int result;
   FILE *source_file;
   if ((source_file=fopen(file_name,"r"))==NULL) result=0;
   else {
      result=1;
      fclose(source_file);
   }
   return result;
}

/* codifica un file */
void code(char source_file_name[MAX_LENGTH],char worm[MAX_LENGTH]) {
   int worm_length=strlen(worm),j,i=0;
   FILE *source_file=fopen(source_file_name,"r");
   FILE *output_file=fopen("file_codificato.txt","w");
   char c,next_worm_char,code_char;
   while ((c=fgetc(source_file))!=EOF) {
      if(isalpha(c)!=0) {
         code_char=c;
         next_worm_char=worm[i++]-'A';
         for (j=0;j<next_worm_char;j++) {
            if(code_char>='A' && code_char<='Z') {
               if(code_char=='Z') code_char='A';
               else code_char++;
            }
            else if(code_char>='a' && code_char<='z') {
               if(code_char=='z') code_char='a';
               else code_char++;
            }
         }
         if (i==worm_length) i=0;
         fputc(code_char,output_file);
      }
      else {
         fputc(c,output_file);
      }
   }
   fclose(source_file);
   fclose(output_file);
}

/* decodifica un file */
void decode(char source_file_name[MAX_LENGTH],char worm[MAX_LENGTH]) {
   int worm_length=strlen(worm),j,i=0;
   FILE *source_file=fopen(source_file_name,"r");
   FILE *output_file=fopen("file_decodificato.txt","w");
   char c,next_worm_char,decode_char;
   while ((c=fgetc(source_file))!=EOF) {
      if(isalpha(c)!=0) {
         decode_char=c;
         next_worm_char=worm[i++]-'A';
         for (j=next_worm_char;j>0;j--) {
            if(decode_char>='A' && decode_char<='Z') {
               if(decode_char=='A') decode_char='Z';
               else decode_char--;
            }
            else if(decode_char>='a' && decode_char<='z') {
               if(decode_char=='a') decode_char='z';
               else decode_char--;
            }
         }
         if (i==worm_length) i=0;
         fputc(decode_char,output_file);
      }
      else {
         fputc(c,output_file);
      }
   }
   fclose(source_file);
   fclose(output_file);
}



Merge sort

Il merge sort, ordinamento a fusione, così come il quick sort, si basa sul paradigma del divide et impera. Il problema (nel nostro caso di ordinamento) viene suddiviso in tanti sottoproblemi di difficoltà man mano inferiore (l'insieme iniziale viene cioè suddiviso). Il merge sort opera dividendo l'array da ordinare in due met à e affina tale partizione fi no ad isolare ogni singolo elemento. La successiva fase, quindi, prevede la costruzione di un array ordinato operando una vera e propria fusione degli insiemi che man mano vengono ordinati. Di seguito propongo una realizzazione dell'algoritmo in C:

/* mergesort */
#include <stdio.h>

#define LENGTH 10

void mergeSort(int *array, int begin, int end);
void merge(int *array,int begin, int middle, int end);

int main(void) {
   int i,array[LENGTH]={1,8,4,0,2,5,6,3,7,9};
   mergeSort(array,0,LENGTH);
   printf("array: ");
   for (i=0;i<LENGTH;i++)
      printf("%d, ",array[i]);
   printf("\b\b;\n");
   return 0;
}

void mergeSort(int *array, int begin, int end) {
   int middle;
   if (begin<end) {
      middle=(end+begin)/2;
      mergeSort(array,begin,middle);
      mergeSort(array,middle+1,end);
      merge(array,begin,middle,end);
   }
}

void merge(int *array,int begin, int middle, int end) {
   int i,j,k,temp[LENGTH];
   i=begin;
   j=middle+1;
   k=0;
   while ((i<=middle) && (j<=end)) {
      if (array[i]<=array[j])
         temp[k++]=array[i++];
      else
         temp[k++]=array[j++];
   }
   while (i<=middle)
      temp[k++]=array[i++];
   while (j<=end)
      temp[k++]=array[j++];
   for (k=begin;k<=end;k++)
      array[k]=temp[k-begin];
}


Quick sort

Il quick sort, ordinamento rapido, si basa sul paradigma divide et impera. Durante le prime istruzioni l'algoritmo si preoccupa di scegliere un elemento dell'array come pivot (perno) e partiziona la sequenza in due sottoinsiemi. Il primo sottoinsieme conterr à tutti gli elementi dell'array che sono minori o uguali al pivot scelto. Il secondo sottoinsieme, invece, conterrà tutti gli elementi dell'array che sono maggiori del pivot. A tale proposito una funzione per la partizione fa scorrere due indici (uno di questi parte dal primo elemento dell'array, il secondo dall'ultimo). Gli indici vengono incrementati (il primo) e decrementati (il secondo) fi nch è viene rispettata la condizione d'ordine nei confronti del pivot.Non appena ciò non è possibile, è evidente che è necessario scambiare i due elementi puntati dai rispettivi indici. Quando i due indici, a seguito dei rispettivi incrementi e decrementi, si incrociano la procedura per la partizione si arresta e va allora richiamata, ricorsivamente sul primo sottoinsieme e sul secondo, fino a ordinare l'intero vettore. Di seguito propongo una realizzazione dell'algoritmo in linguaggio C:

/* quicksort */
#include <stdio.h>

#define LENGTH 10

void quickSort (int *array, int left, int right);
void swap(int *x, int *y);

int main (void) {
   int i,array[LENGTH]={1,8,4,0,2,5,6,3,7,9};
   quickSort(array,0,LENGTH-1);
   printf("array: ");
   for (i=0;i<LENGTH;i++)
      printf("%d, ",array[i]);
   printf("\b\b;\n");
}

void quickSort (int *array, int left, int right) {
   int i=left, j=right;
   int pivot=array[(left+right)/2];
   do {
      while (array[i]<pivot) i++;
      while (array[j]>pivot) j--;
      if (i<=j) {
         swap(&array[i],&array[j]);
         i++; j--;
      }
   } while (i<=j);
   if (left<j) quickSort(array,left,j);
   if (i<right) quickSort(array,i,right);
}

void swap(int *x, int *y) {
   int temp=*x;
   *x=*y;
   *y=temp;
}


Bubble sort

Il bubble sort, ordinamento a bolle, realizza l'ordinamento di una lista di valori eseguendo confronti fra coppie adiacenti. L'esito del confronto stabilisce il valore da spostare, man mano verso il fondo della lista. Se in una iterazione, ancora prima di scorrere tutte le coppie, non avvengono scambi la lista è allora già ordinata! Queste le fasi previste dall'algoritmo:

• inizializzare una variabile per stabilire se durante una iterazione avviene almeno uno scambio fra coppie adiacenti e un indice che punta all'ultimo elemento del vettore ordinato;
• scorrere la lista, confrontando le coppie adiacenti ed effettuando, eventualmente, lo scambio (segnando l'evento nell'apposita variabile) se queste non sono tra loro ordinate;
• ripetere il precedente passaggio arrestando la serie di confronti al valore precedentemente già ordinato e puntato dall'indice (che man mano verrà quindi decrementato);

L'algoritmo, allora, termina quando l'indice che punta l'ultimo elemento ordinato raggiunge la testa della lista oppure, come già detto, se in una iterazione non si verificano scambi. Di seguito propongono una realizzazione dell'algoritmo in linguaggio C:

/* bubblesort */
#include <stdio.h>
#include <stdbool.h>

#define LENGTH 10

void bubbleSort(int *array,int length);
void swap(int *x, int *y);

int main(void) {
   int i,array[LENGTH]={1,8,4,0,2,5,6,3,7,9};
   bubbleSort(array,LENGTH);
   printf("array: ");
   for (i=0;i<LENGTH;i++)
      printf("%d, ",array[i]);
   printf("\b\b;\n");
   return 0;
}

void bubbleSort(int *array,int length) {
   int i,temp,step=0;
   bool change;
   do {
      change=false;
      for (i=0;i<length-1-step;i++) {
         if (array[i]>array[i+1]) {
            swap(&array[i],&array[i+1]);
            change=true;
         }
      }
      step++;
   }
   while(change==true);
}

void swap(int *x, int *y) {
   int temp=*x;
   *x=*y;
   *y=temp;
}


Selection sort

Il selection sort, ordinamento per selezione, è uno degli algoritmi di ordinamento più intuitivi (e di facile realizzazione). L'ordinamento avviene selezionando ad ogni iterazione il valore più piccolo e scambiando quest'ultimo con il valore in testa alla lista da ordinare e non ancora ordinato (prima iterazione). Le successive iterazioni effettueranno, allora, la ricerca del valore più piccolo su un insieme di valori sempre più ridotti. Un indice indica la posizione della lista che si sta ordinando. Ad ogni iterazione, dunque, la lista ordinata aumenta di un valore fino a prevedere tutti i valori della lista di partenza. Queste le fasi previste dall'algoritmo:

• inizializzare un puntatore i che va da 0 ad n-1, con n lunghezza dell'array (il primo elemento dell'array ha indice 0);
• cercare il valore più piccolo nell'array;
• scambiare l'elemento più piccolo, appena trovato, con l'elemento puntato da i;
• incrementare i e ripetere la ricerca del valore più piccolo fino a scorrere tutti gli elementi dell'array;

Di seguito propongo una realizzazione dell'algoritmo in linguaggio C:

/* selectionsort */
#include <stdio.h>

#define LENGTH 10

void selectionSort(int *array,int length);
int search_min(int *array,int begin,int end);
void swap(int *x, int *y);

int main(void) {
   int i,array[LENGTH]={1,8,4,0,2,5,6,3,7,9};
   selectionSort(array, LENGTH);
   printf("array: ");
   for (i=0;i<LENGTH;i++)
      printf("%d, ",array[i]);
   printf("\b\b;\n");
   return 0;
}

void selectionSort(int *array,int length) {
   int i,i_min;
   for (i=0;i<length;i++) {
      if ((i_min=search_min(array,i,length))==-1)
         printf("Errore nella chiamata alla funzione!");
      else swap(&array[i],&array[i_min]);
   }
}

int search_min(int *array,int begin,int end) {
   int i,temp_i;
   if (begin<end) {
      temp_i=begin;
      for (i=begin+1;i<end;i++) {
         if (array[i]<array[temp_i]) temp_i=i;
      }
      return temp_i;
   }
   else return -1;
}

void swap(int *x, int *y) {
   int temp=*x;
   *x=*y;
   *y=temp;
}


Linguaggio C

In questa pagina trovate una preview del libro pubblicato su issuu. La lettura può avvenire attraverso la pagina suggerita oppure scaricando il file pdf allegato alla stessa (per il download è sufficiente accedere alla pagina e cliccare su "Download"). Il documento è rilasciato seguendo i termini della Licenza per Documentazione libera GNU. Trovate la licenza all'interno del documento. Qui trovate il codice sorgente per generare il documento (file tex per LaTex). Lasciatemi un messaggio per le eventuali correzioni.