Mandelbrot mat intera e shift bit

Questo e' un lavoro intermedio per vedere se riesco a ricreare l'insieme di Mandelbrot in Assembly x86 senza utilizzare i comandi del coprocessore matematico (come per esempio qui) ed utilizzando per le moltiplicazione e divisioni le operazioni di shift dei bit

Per prima cosa il moltplicatore e' impostato come una potenza di due (nell'esempio come 2^7)
Cio' permette di evitare il piu' possibile  moltiplicazioni e divisioni che possono essere sostituite da shift a destra per la divisione e shift a sinistra per la moltiplicazione (tipicamente per moltiplicare e dividere un numero per due e' sufficiente effettuare lo shift dei bit di una posizione)

Un altro trucco e' quello di utilizzare una tabella precalcolata dei quadrati dei primi 700 numeri.
Per la matrice deve essere gestita anche la possibilita' dei quadranti negativi... per simulare il comando abs di C e' stato usato il bit shit con la seguente formula

 int x_abs = (x^(x>>31))-(x>>31);



---------------------------------------------------------------------
#include <SDL/SDL.h>
#include <math.h>

#define SCREEN_WIDTH 159
#define SCREEN_HEIGHT 99

#define SCREEN_DEPTH 8

unsigned char iterazioni = 15; //byte
unsigned char keypress = 0; //byte
unsigned char k; //byte

short int a,b,nx,ny;  // dimensione word 16 bit
int t,limite,x,y;     // 32 bit

unsigned short int i,j,de,di; // dimensione word 16 bit

unsigned int inizio,fine = 0;

int main ()
{
SDL_Surface *screen;
Uint8  *p;


SDL_Init(SDL_INIT_VIDEO);
screen = SDL_SetVideoMode(SCREEN_WIDTH, SCREEN_HEIGHT, SCREEN_DEPTH, SDL_SWSURFACE);


//-------------------------------------------------------
unsigned int square[]={
0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100,
121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441,
484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1024,
1089, 1156, 1225, 1296, 1369, 1444, 1521, 1600, 1681, 1764, 1849,
1936, 2025, 2116, 2209, 2304, 2401, 2500, 2601, 2704, 2809, 2916,
3025, 3136, 3249, 3364, 3481, 3600, 3721, 3844, 3969, 4096, 4225,
4356, 4489, 4624, 4761, 4900, 5041, 5184, 5329, 5476, 5625, 5776,
5929, 6084, 6241, 6400, 6561, 6724, 6889, 7056, 7225, 7396, 7569,
7744, 7921, 8100, 8281, 8464, 8649, 8836, 9025, 9216, 9409, 9604,
9801, 10000, 10201, 10404, 10609, 10816, 11025, 11236, 11449, 11664, 11881,
12100, 12321, 12544, 12769, 12996, 13225, 13456, 13689, 13924, 14161, 14400,
14641, 14884, 15129, 15376, 15625, 15876, 16129, 16384, 16641, 16900, 17161,
17424, 17689, 17956, 18225, 18496, 18769, 19044, 19321, 19600, 19881, 20164,
20449, 20736, 21025, 21316, 21609, 21904, 22201, 22500, 22801, 23104, 23409,
23716, 24025, 24336, 24649, 24964, 25281, 25600, 25921, 26244, 26569, 26896,
27225, 27556, 27889, 28224, 28561, 28900, 29241, 29584, 29929, 30276, 30625,
30976, 31329, 31684, 32041, 32400, 32761, 33124, 33489, 33856, 34225, 34596,
34969, 35344, 35721, 36100, 36481, 36864, 37249, 37636, 38025, 38416, 38809,
39204, 39601, 40000, 40401, 40804, 41209, 41616, 42025, 42436, 42849, 43264,
43681, 44100, 44521, 44944, 45369, 45796, 46225, 46656, 47089, 47524, 47961,
48400, 48841, 49284, 49729, 50176, 50625, 51076, 51529, 51984, 52441, 52900,
53361, 53824, 54289, 54756, 55225, 55696, 56169, 56644, 57121, 57600, 58081,
58564, 59049, 59536, 60025, 60516, 61009, 61504, 62001, 62500, 63001, 63504,
64009, 64516, 65025, 65536, 66049, 66564, 67081, 67600, 68121, 68644, 69169,
69696, 70225, 70756, 71289, 71824, 72361, 72900, 73441, 73984, 74529, 75076,
75625, 76176, 76729, 77284, 77841, 78400, 78961, 79524, 80089, 80656, 81225,
81796, 82369, 82944, 83521, 84100, 84681, 85264, 85849, 86436, 87025, 87616,
88209, 88804, 89401, 90000, 90601, 91204, 91809, 92416, 93025, 93636, 94249,
94864, 95481, 96100, 96721, 97344, 97969, 98596, 99225, 99856, 100489, 101124,
101761, 102400, 103041, 103684, 104329, 104976, 105625, 106276, 106929, 107584, 108241,
108900, 109561, 110224, 110889, 111556, 112225, 112896, 113569, 114244, 114921, 115600,
116281, 116964, 117649, 118336, 119025, 119716, 120409, 121104, 121801, 122500, 123201,
123904, 124609, 125316, 126025, 126736, 127449, 128164, 128881, 129600, 130321, 131044,
131769, 132496, 133225, 133956, 134689, 135424, 136161, 136900, 137641, 138384, 139129,
139876, 140625, 141376, 142129, 142884, 143641, 144400, 145161, 145924, 146689, 147456,
148225, 148996, 149769, 150544, 151321, 152100, 152881, 153664, 154449, 155236, 156025,
156816, 157609, 158404, 159201, 160000, 160801, 161604, 162409, 163216, 164025, 164836,
165649, 166464, 167281, 168100, 168921, 169744, 170569, 171396, 172225, 173056, 173889,
174724, 175561, 176400, 177241, 178084, 178929, 179776, 180625, 181476, 182329, 183184,
184041, 184900, 185761, 186624, 187489, 188356, 189225, 190096, 190969, 191844, 192721,
193600, 194481, 195364, 196249, 197136, 198025, 198916, 199809, 200704, 201601, 202500,
203401, 204304, 205209, 206116, 207025, 207936, 208849, 209764, 210681, 211600, 212521,
213444, 214369, 215296, 216225, 217156, 218089, 219024, 219961, 220900, 221841, 222784,
223729, 224676, 225625, 226576, 227529, 228484, 229441, 230400, 231361, 232324, 233289,
234256, 235225, 236196, 237169, 238144, 239121, 240100, 241081, 242064, 243049, 244036,
245025, 246016, 247009, 248004, 249001, 250000, 251001, 252004, 253009, 254016, 255025,
256036, 257049, 258064, 259081, 260100, 261121, 262144, 263169, 264196, 265225, 266256,
267289, 268324, 269361, 270400, 271441, 272484, 273529, 274576, 275625, 276676, 277729,
278784, 279841, 280900, 281961, 283024, 284089, 285156, 286225, 287296, 288369, 289444,
290521, 291600, 292681, 293764, 294849, 295936, 297025, 298116, 299209, 300304, 301401,
302500, 303601, 304704, 305809, 306916, 308025, 309136, 310249, 311364, 312481, 313600,
314721, 315844, 316969, 318096, 319225, 320356, 321489, 322624, 323761, 324900, 326041,
327184, 328329, 329476, 330625, 331776, 332929, 334084, 335241, 336400, 337561, 338724,
339889, 341056, 342225, 343396, 344569, 345744, 346921, 348100, 349281, 350464, 351649,
352836, 354025, 355216, 356409, 357604, 358801, 360000, 361201, 362404, 363609, 364816,
366025, 367236, 368449, 369664, 370881, 372100, 373321, 374544, 375769, 376996, 378225,
379456, 380689, 381924, 383161, 384400, 385641, 386884, 388129, 389376, 390625, 391876,
393129, 394384, 395641, 396900, 398161, 399424, 400689, 401956, 403225, 404496, 405769,
407044, 408321, 409600, 410881, 412164, 413449, 414736, 416025, 417316, 418609, 419904,
421201, 422500, 423801, 425104, 426409, 427716, 429025, 430336, 431649, 432964, 434281,
435600, 436921, 438244, 439569, 440896, 442225, 443556, 444889, 446224, 447561, 448900,
450241, 451584, 452929, 454276, 455625, 456976, 458329, 459684, 461041, 462400, 463761,
465124, 466489, 467856, 469225, 470596, 471969, 473344, 474721, 476100, 477481, 478864,
480249, 481636, 483025, 484416, 485809, 487204, 488601, 490000, 491401, 492804, 494209,
495616, 497025, 498436, 499849, 501264, 502681, 504100, 505521, 506944, 508369, 509796,
511225, 512656, 514089, 515524, 516961, 518400, 519841, 521284, 522729, 524176, 525625,
527076, 528529, 529984, 531441, 532900, 534361, 535824, 537289, 538756, 540225, 541696,
543169, 544644, 546121, 547600, 549081, 550564, 552049, 553536, 555025, 556516, 558009,
559504, 561001, 562500, 564001, 565504, 567009, 568516, 570025, 571536, 573049, 574564
};

  inizio = SDL_GetTicks();

  int bit = 7;

  a = -2<<bit;
  de = 2;
  di = 3;

  limite = 1<<(bit+2);

  for (i=0;i<SCREEN_WIDTH;i++)
  {
  a=a+de;
  b=-154;
  for (j=0;j<SCREEN_HEIGHT;j++)
    {
    b=b+di;
    x=0;
    y=0;
    for (k=1;k<iterazioni;k++)
        {
        int x_abs = (x^(x>>31))-(x>>31);
        int y_abs = (y^(y>>31))-(y>>31);
        nx = (square[x_abs]>>bit) - (square[y_abs]>>bit) + a;

        y = ((x*y)>>(bit-1))+b;

        int nx_abs = (nx^(nx>>31))-(nx>>31);
        y_abs = (y^(y>>31))-(y>>31);
        t = (square[nx_abs]>>bit) + (square[y_abs]>>bit);
        //t = (square[abs(nx)]>>bit) + (square[abs(y)]>>bit);
        //t = (nx*nx>>bit) + (y*y>>bit);
        if (t>limite)
            {
            //plot
            p = (Uint8 *)screen->pixels + j * screen->pitch + i * screen->format->BytesPerPixel;
            *p=255;
            k =26;
            }
        x=nx;
        }
  }
}
SDL_Flip(screen);

fine = SDL_GetTicks();
printf("Esecuzione 5: %d\n", fine-inizio);

bool done=false;
while (!done)
    {
        // message processing loop
        SDL_Event event;
        while (SDL_PollEvent(&event))
        {
            switch (event.type)
            {
            case SDL_QUIT:
                done = true;
                break;
            case SDL_KEYDOWN:
                {
                    // exit if ESCAPE is pressed
                    if (event.key.keysym.sym == SDLK_ESCAPE)
                        done = true;
                    break;
                }
            } // end switch
        } // end of message proc
}
//---------------------------------------------

SDL_Quit();

return(0);
}

C4Droid

C4Droid e' la prima applicazione in assoluto che abbia acquistato (2.29 euro) e devo ammettere che ne vale la pena

L'applicazione permette di programmare all'interno di un terminale Android in C/C++ con Gcc come compilatore ed con alcune librerie di uso comune all'interno di Linux come SDL e Qt. In questo modo ci si svincola dall'impiego di Java e dalla macchina virtuale Dalvik per fare applicazione di livello piu' basso come e' possibile fare con l'NDK

Per mettere alla prova il compilatore ho preso il sorgente del post che permette di disegnare l'insieme di Mandelbrot

Il codice e' stato copiato ed incollato senza nessuna modifica, quindi compilato ed eseguito

Il risultato e' riportato nella immagine sottostante

Come si puo' osservare il risultato e' quello atteso. Il tempo di esecuzione, che su un pc attuale non e' quasi misurabile dato che il risultato e' quasi istantaneo, nel telefono Samsung GT-S5570i e' di circa 18 secondi

Con lo stesso compilatore si puo' usare Ncurses. Sempre prendendo a prestito da un precedente post si puo' ottenere

La cosa divertente e' che con questo compilatore si riesce a superare il controllo della latenza di Dalvik. In pratica di norma Android interrompe una applicazione se questa per circa 30 secondi non restituisce la possibilita' di interazione all'utente

L'immagine sottostante e' stata effettuata mediante un calcolo di circa 2 minuti e 25 secondi ed e' stata terminata senza nessuna segnalazione di anomalia da parte del sistema operativo

Un buon acquisto in fine dei conti anche se in fine dei conti si tratta di un giochino piu' che di uno strumento di produzione

Intel C Compiler vs GCC in Mandelbrot

Ho provato a verificare la differenza tra Gcc ed il compilatore Intel C++ (icc) per quanto riguarda la velocita' e l'ottimizzazione dei calcoli
Per fare cio' e' stato impiegato il programma per generare l'insieme di Mandelbrot gia' presentato in un precedente post usando gli stessi switch di compilazione all'interno del file make



Makefile
------------------------------------------------------
main: mand_sdl.c
    /opt/intel/bin/icc -Wall -O3 mand_sdl.c -o mand_sdl_icc -lSDL
    gcc -Wall -O3 mand_sdl.c -o mand_sdl_gcc -lSDL
------------------------------------------------------

Il programma e' il seguente
 mand_sdl.c
------------------------------------------------------
 #include "SDL/SDL.h"
#include <stdio.h>

#define SCREEN_WIDTH 640
#define SCREEN_HEIGHT 480
#define SCREEN_DEPTH 8

float re_min = -2.0;
float im_min = -1.2;

float re_max = 1.0;
float im_max = 1.2;
int iterazioni = 255;


float a,b;
float x,y,x_new,y_new;

int test;

int k,j,i;

int keypress = 0;


int main() {

SDL_Surface *screen;
Uint8       *p;

float re_factor = (re_max-re_min);
float im_factor = (im_max-im_min);
   
SDL_Init(SDL_INIT_VIDEO);
screen = SDL_SetVideoMode(SCREEN_WIDTH, SCREEN_HEIGHT, SCREEN_DEPTH, SDL_SWSURFACE);

for (i=0;i<SCREEN_HEIGHT;i++)
    {
    for (j=0;j<SCREEN_WIDTH;j++)
        {
        a = re_min+(j*re_factor/SCREEN_WIDTH);  
        b = im_min+(i*im_factor/SCREEN_HEIGHT);
      
        x = 0;
        y = 0;
        test = 0;
      
        for (k=0;k<iterazioni;k++)
            {
            x_new = (x*x)-(y*y)+a;
            y_new = (2*x*y)+b;
            if (((x_new*x_new)+(y_new*y_new))>4)
                {
                test = k;
                p = (Uint8 *)screen->pixels + i * screen->pitch + j * screen->format->BytesPerPixel;
                *p=(k%255);
                break;
                }
            x = x_new;
            y = y_new;
            }
          
        }

    }
SDL_Flip(screen);

printf("Finito\n\r");

SDL_Quit();

return(0);

}

------------------------------------------------------
Per calcolare il tempo di esecuzione e' stato usato il comando time che misura il tempo tra l'inizio e la fine dell'esecuzione

time  mand_sdl_gcc
time mand_sdl_icc

i risultati sono decisamente schiaccianti. Intel vince in velocita'

Intel
Totale 0.974
User   0.624
Sys    0.024

Gcc
Totale 1.325
User   0.948
Sys    0.020


Link al progetto

Esempio insieme di Mandelbrot in C/SDL

Un esempio di creazione dell'insieme di Mandelbrot impiegando la libreria SDL per la parte grafica

--------------------------------------------

#include "SDL/SDL.h"
#include <stdio.h>

#define SCREEN_WIDTH 640
#define SCREEN_HEIGHT 480
#define SCREEN_DEPTH 8

float re_min = -2.0;
float im_min = -1.2;

float re_max = 1.0;
float im_max = 1.2;
int iterazioni = 255;


float a,b;
float x,y,x_new,y_new;

int test;

int k,j,i;

int keypress = 0;


int main() {

SDL_Surface *screen;
Uint8       *p;
SDL_Event event;

float re_factor = (re_max-re_min);
float im_factor = (im_max-im_min);
     
SDL_Init(SDL_INIT_VIDEO);
screen = SDL_SetVideoMode(SCREEN_WIDTH, SCREEN_HEIGHT, SCREEN_DEPTH, SDL_SWSURFACE);

for (i=0;i<SCREEN_HEIGHT;i++)
{
for (j=0;j<SCREEN_WIDTH;j++)
{
a = re_min+(j*re_factor/SCREEN_WIDTH);
b = im_min+(i*im_factor/SCREEN_HEIGHT);

x = 0;
y = 0;
test = 0;

for (k=0;k<iterazioni;k++)
{
x_new = (x*x)-(y*y)+a;
y_new = (2*x*y)+b;
if (((x_new*x_new)+(y_new*y_new))>4)
{
test = k;
p = (Uint8 *)screen->pixels + i * screen->pitch + j * screen->format->BytesPerPixel;
*p=(k%255);
break;
}
x = x_new;
y = y_new;
}
       
}

}
SDL_Flip(screen);

printf("Finito\n\r");

while (!keypress)
{
while (SDL_PollEvent(&event))
{
switch (event.type)
{
case SDL_KEYDOWN:
keypress = 1;
}
}
}
SDL_Quit();

return(0);

}
--------------------------------------------

il progetto puo' essere scaricato a questo indirizzo link

Compilare SDL da riga di comando

il programma di esempio di SDL deve essere modificato nella riga di include in quanto  il file .h si trova in una sottodirectory (si devono installare le librerie di sviluppo indicate qui)

per la compilazione si deve poi usare la stringa

gcc -Wall -O3 -lSDL SDLTest.c -o SDLTest
-------------------------------------------------

#include <stdio.h>
#include <SDL/SDL.h>

#define WIDTH 640
#define HEIGHT 480
#define BPP 4
#define DEPTH 32

void setpixel(SDL_Surface *screen, int x, int y, Uint8 r, Uint8 g, Uint8 b)
{
    Uint32 *pixmem32;
    Uint32 colour;  

    colour = SDL_MapRGB( screen->format, r, g, b );
  
    pixmem32 = (Uint32*) screen->pixels  + y + x;
    *pixmem32 = colour;
}


void DrawScreen(SDL_Surface* screen, int h)
{ 
    int x, y, ytimesw;
  
    if(SDL_MUSTLOCK(screen)) 
    {
        if(SDL_LockSurface(screen) < 0) return;
    }

    for(y = 0; y < screen->h; y++ ) 
    {
        ytimesw = y*screen->pitch/BPP;
        for( x = 0; x < screen->w; x++ ) 
        {
            setpixel(screen, x, ytimesw, (x*x)/256+3*y+h, (y*y)/256+x+h, h);
        }
    }

    if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);
  
    SDL_Flip(screen); 
}


int main(int argc, char* argv[])
{
    SDL_Surface *screen;
    SDL_Event event;
  
    int keypress = 0;
    int h=0; 
  
    if (SDL_Init(SDL_INIT_VIDEO) < 0 ) return 1;
   
    if (!(screen = SDL_SetVideoMode(WIDTH, HEIGHT, DEPTH, SDL_FULLSCREEN|SDL_HWSURFACE)))
    {
        SDL_Quit();
        return 1;
    }
  
    while(!keypress) 
    {
         DrawScreen(screen,h++);
         while(SDL_PollEvent(&event)) 
         {      
              switch (event.type) 
              {
                  case SDL_QUIT:
             keypress = 1;
             break;
                  case SDL_KEYDOWN:
                       keypress = 1;
                       break;
              }
         }
    }

    SDL_Quit();
  
    return 0;
}

Compilare SDL con Code::Blocks

Per compilare con Code::Blocks programmi con dipendenza in SDL sotto Debian 6.0 e' sufficiente installare mediante apt-get le librerie di sviluppo sotto riportate

libsdl-sound1.2-dev

libsdl1.2-dev

libsdl-image1.2-dev 

libsdl-mixer1.2-dev

libsdl-net1.2-dev

libsdl-ttf2.0-dev

libsdl-ttf2.0-dev