This code generates this picture http://allrgb.com/dla which uses each 2^24 color once and only once.
DLA rule is tweaked a bit to generate nice picture.
Save as dla.cc , just compile it cc dla.cc, and run "a.out Number.of.Seeds"
// Bits per plane. Must be even and <=8, namely either 2, 4, 6, 8 //Uncomment these for 4096x4096 //#define CBIT 8 //Addressing scheme 4 is fastest for CBIT=8 //#define ADR_SCHEME4 // Use these for 512x512 test #define CBIT 6 //Addressing scheme 0 is fastest for CBIT=6 #define ADR_SCHEME0 ///////////////////////////////////////////////////// // no need to edit below #define CADR_SCHEME0 // Misc. consts #define VMAX (1<<CBIT) #define CBMASK (VMAX-1) #define LBIT (CBIT+CBIT/2) #define L (1<<LBIT) #define L2 (L*L) #define L2MASK (L2-1) #define LMASK (L-1) #define LMASKY (L2MASK ^ LMASK) // Manage list of unused colors int nemp_c; int emp_c[L2]; void init_emp() { int i; for(i=0;i<L2;i++) { emp_c[i]=i; } nemp_c=L2; } //Address conversion // x, y ->3char #define BTMOV(x, mask, sh) (((x)&mask)<<sh) #define BTMOV2(x, mask, sh) (((x)&mask)>>sh) // c00000 c0000 c000 c00 c0 c // 8421 8421 8421 8421 8421 8421 // yyxx yyxx yyxx yyxx yyxx yyxx #ifdef ADR_SCHEME0 #define XY2ADR(x,y) ((x)|((y)*L)) #define ADR2XY(a,x,y) { x=a&(L-1);y=a/L;} #endif // 4bit #ifdef ADR_SCHEME4 #define XY2ADR(x,y) (\ BTMOV(x,0xf, 0) | BTMOV(y,0xf, 4) | \ BTMOV(x,0xf0, 4) | BTMOV(y,0xf0, 8) | \ BTMOV(x,0xf00,8) | BTMOV(y,0xf00,12)) #define ADR2XY(a,x,y) {\ x=BTMOV2((a),0x0f,0) |BTMOV2((a),0xf00,4) |BTMOV2((a),0xf0000,8);\ y=BTMOV2((a),0xf0,4) |BTMOV2((a),0xf000,8) |BTMOV2((a),0xf00000,12);} #endif // 3bit #ifdef ADR_SCHEME3 #define XY2ADR(x,y) (\ BTMOV(x,07, 0) | BTMOV(y,07, 3) |\ BTMOV(x,070, 3) | BTMOV(y,070,6) |\ BTMOV(x,0700,6) | BTMOV(y,0700,9) |\ BTMOV(x,07000,9) | BTMOV(y,07000,12)) #define ADR2XY(a,x,y) {\ x=BTMOV2((a),07,0) |BTMOV2((a),0700,3) |BTMOV2((a),070000,6) |BTMOV2((a),07000000,9);\ y=BTMOV2((a),070,3) |BTMOV2((a),07000,6) |BTMOV2((a),0700000,9) |BTMOV2((a),070000000,12);} #endif // 2bit #ifdef ADR_SCHEME2 #define XY2ADR(x,y) (\ BTMOV(x,0x3, 0) | BTMOV(y,0x3, 2) | BTMOV(x,0xc,2) | BTMOV(y,0xc,4) |\ BTMOV(x,0x30,4) | BTMOV(y,0x30,6) | BTMOV(x,0xc0,6)|BTMOV(y,0xc0,8) |\ BTMOV(x,0x300,8) | BTMOV(y,0x300,10) | BTMOV(x,0xc00,10)|BTMOV(y,0xc00,12) ) #define ADR2XY(a,x,y) {\ x=BTMOV2(a,0x03,0) |BTMOV2(a,0x30,2) |BTMOV2(a,0x300,4)|\ BTMOV2(a,0x3000,6)|BTMOV2(a,0x30000,8)|BTMOV2(a,0x300000,10);\ y=BTMOV2(a,0x0c,2) |BTMOV2(a,0xc0,4) |BTMOV2(a,0xc00,6)|\ BTMOV2(a,0xc000,8)|BTMOV2(a,0xc0000,10)|BTMOV2(a,0xc00000,12);} #endif ////////////////////////////////////////////////////////// #ifdef CADR_SCHEME4 #define rgb2idx(r,g,b) (\ BTMOV(r,0x0f,0) | BTMOV(g,0x0f,4) | BTMOV(b, 0x0f,8) |\ BTMOV(r,0xf0,8) | BTMOV(g,0xf0,12) | BTMOV(b, 0xf0,16) \ ) #endif #ifdef CADR_SCHEME0 #define rgb2idx(r,g,b) ((r)|((g)<<CBIT)|((b)<<(CBIT*2))) #define IDX2RGB(c,r,g,b) {r=(c)&CBMASK; g=((c)>>CBIT)&CBMASK;b=((c)>>(CBIT*2))&CBMASK;} #endif ///////////////////////////////////////////////////// // global variables block typedef unsigned char rgbtype; // main color data rgbtype colr[L2],colg[L2], colb[L2]; rgbtype *col3[3]={colr, colg, colb}; #include <math.h> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <sys/time.h> // for timing int getmsec() { static int sec0=0,usec0=0; struct timeval tv; struct timezone tz; gettimeofday(&tv,&tz); return tv.tv_sec*1000+tv.tv_usec/1000; //int res=(tv.tv_sec-sec0)*1000000+(tv.tv_usec-usec0); //sec0=tv.tv_sec; //usec0=tv.tv_usec; //return res; } //////////// // DLA var unsigned char solid[L2]; int cidx[L2]; char cidx0[L2]; int dwid; void place_solid(int x,int y, int r, int g, int b, int sol) { int x1=(x-1)&LMASK; int x2=(x+1)&LMASK; int y1=(y-1)&LMASK; int y2=(y+1)&LMASK; int ad=XY2ADR(x,y); int c=rgb2idx(r,g,b); cidx[c]=ad; cidx0[c]=1; solid[ad]=1; colr[ad]=r; colg[ad]=g; colb[ad]=b; ad=XY2ADR(x1,y);if(solid[ad]==0)solid[ad]=sol; ad=XY2ADR(x2,y);if(solid[ad]==0)solid[ad]=sol; ad=XY2ADR(x,y1);if(solid[ad]==0)solid[ad]=sol; ad=XY2ADR(x,y2);if(solid[ad]==0)solid[ad]=sol; } int init_misc(int nc, double rt) { if(nc!=1)dwid = L; else dwid=64; if(dwid>L)dwid=L; int i; int maxv=(int)(VMAX*rt); int res=0; for(i=0;i<L2;i++) { solid[i]=0; cidx[i]=-1; cidx0[i]=0; int r,g,b; IDX2RGB(i,r,g,b); int max=r; int min=r; if(max<g)max=g; if(max<b)max=b; if(min>g)min=g; if(min>b)min=b; // reserve low-satulation colors int sat=max-min; if (sat < maxv) { cidx[i]=-2; cidx0[i]=1; res++; } } //place random seeds for(i=0;i<nc;i++) { int x=(rand()>>4)&LMASK; int y=(rand()>>4)&LMASK; if(nc==1) { x=y=L/2; } int c; while(1) { c=(rand()>>4)&L2MASK; if(cidx0[c]== 0)break; } printf("#Init Place %d\n",i); int r,g,b; IDX2RGB(c,r,g,b); place_solid(x,y, r,g,b,2); } return res; } // dump color to a file void dump(int idx, rgbtype *rr, rgbtype *gg, rgbtype *bb) { bool do_stuff = true; if (do_stuff) { //init_cidx(); char fn[128]; sprintf(fn, "%04d.ppm",idx); FILE *fp; unsigned char *pbuf = (unsigned char *)malloc(L2*3); fp=fopen(fn,"w"); if (fp==NULL) { printf("cannot open %s for dump\n",fn); exit(1); } int i; int vv = 255/(VMAX-1); printf("#Dump %s, color scale *%d Size %f Mb\n",fn, vv, L2*3e-6); int x,y; for(i=0;i<L2;i++) { ADR2XY(i, x, y); int ad= (x+y*L)*3; pbuf[ad+0] = vv*rr[i]; pbuf[ad+1] = vv*gg[i]; pbuf[ad+2] = vv*bb[i]; } fprintf(fp, "P6\n%d %d\n255\n", L,L); fwrite(pbuf,1,L2*3,fp); fclose(fp); free(pbuf); } } void dump_small(int idx, rgbtype *rr, rgbtype *gg, rgbtype *bb) { bool do_stuff = true; if (do_stuff) { char fn[128]; sprintf(fn, "ppms/%04d.ppm",idx); FILE *fp; int l00=720; if (l00>L)l00=480; if (l00>L)l00=320; if (l00>L)return; unsigned char *pbuf = (unsigned char *)malloc(l00*l00*3); int *ibuf = (int *)malloc(l00*l00*3*4); int *ibuf2 = (int *)malloc(l00*l00*4); int i; for(i=0;i<l00*l00;i++) { ibuf2[i]=0; ibuf[i*3+0]=0; ibuf[i*3+1]=0; ibuf[i*3+2]=0; } fp=fopen(fn,"w"); if (fp==NULL) { printf("cannot open %s for dump\n",fn); exit(1); } int vv = 255/(VMAX-1); printf("#Dump %s, color scale *%d Size %f Mb\n",fn, vv, l00*l00*3e-6); //Calc for(i=0;i<L2;i++) { int x,y; ADR2XY(i,x,y); int x2 = x*l00/L; int y2 = y*l00/L; int ad = x2+y2*l00; ibuf2[ad]++; ibuf[ad*3+0] += vv*rr[i]; ibuf[ad*3+1] += vv*gg[i]; ibuf[ad*3+2] += vv*bb[i]; } for(i=0;i<l00*l00;i++) { pbuf[i*3+0] = ibuf[i*3+0]/ibuf2[i]; pbuf[i*3+1] = ibuf[i*3+1]/ibuf2[i]; pbuf[i*3+2] = ibuf[i*3+2]/ibuf2[i]; } fprintf(fp, "P6\n%d %d\n255\n", l00,l00); fwrite(pbuf,1,l00*l00*3,fp); fclose(fp); free(pbuf); free(ibuf); free(ibuf2); } } // resume from an image file // or import smaller size image and expand, add lower bit data void load_ppm(char *fn) { char buf[128]; FILE *fp=fopen(fn, "r"); if (fp==NULL) { printf("# cannot open file %s\n",fn); exit(1); } int ll; fgets(buf,99,fp); fgets(buf,99,fp); sscanf(buf, "%d", &ll); fgets(buf,99,fp); printf("#Loading %s L=%d\n",fn, ll); if (ll==L) { //resume printf(" #Same size data\n"); unsigned char *pbuf = (unsigned char *)malloc(L2*3); fread(pbuf,1,L2*3,fp); fclose(fp); int vv = 255/(VMAX-1); printf(" # read complete, color scale /%d\n", vv); int i; int ad,x,y; for(i=0;i<L2;i++) { x=i&(L-1); y=i/L; ad = XY2ADR(x,y); unsigned char *c = &pbuf[i*3]; colr[ad] = c[0]/vv; colg[ad] = c[1]/vv; colb[ad] = c[2]/vv; } free(pbuf); return; } if (ll*ll==L) { // self-similar printf(" # sqrt(L) size data\n"); unsigned char *pbuf = (unsigned char *)malloc(ll*ll*3); fread(pbuf,1,ll*ll*3,fp); fclose(fp); int v2 = (1<<(CBIT/2)); int vv = 255/(v2-1); printf(" # read complete, color scale /%d\n", vv); int x,y; //block for(x=0;x<ll;x++){ for(y=0;y<ll;y++){ int ad1 = (x+y*ll)*3; int r1=(pbuf[ad1 +0]/vv)<<(CBIT/2); int g1=(pbuf[ad1 +1]/vv)<<(CBIT/2); int b1=(pbuf[ad1 +2]/vv)<<(CBIT/2); int xx,yy; for(xx=0;xx<ll;xx++){ for(yy=0;yy<ll;yy++){ int x2=xx; int y2=yy; if (x&1) x2=ll-1-xx; if (y&1) y2=ll-1-yy; int ad0 = (x2+y2*ll)*3; int r=pbuf[ad0 +0]/vv +r1; int g=pbuf[ad0 +1]/vv +g1; int b=pbuf[ad0 +2]/vv +b1; int ad1 = (x*ll+xx)+(y*ll+yy)*L; colr[ad1] = r; colg[ad1] = g; colb[ad1] = b; }} }} free(pbuf); return; } if (ll==L/8) { // expand CBIT-2 image printf(" # 1/8 size data\n"); unsigned char *pbuf = (unsigned char *)malloc(L2*3/64); fread(pbuf,1,L2*3/64,fp); fclose(fp); int ofs[8][8][3]; int x,y; int vv = 255/((VMAX/4)-1); printf(" # read complete, vv=%d\n",vv); // 8x8 optimum solution int ofsR[8][8]; int ofsG[8][8]; int ofsRy[8]={1,0,0,1,2,3,3,2}; int ofsGx[8]={0,0,1,2,3,3,2,1}; int ofsB[8][8]= { {2,3,3,3,3,2,2,2}, {2,3,3,3,3,1,1,1}, {0,1,2,2,2,0,0,0}, {0,1,1,1,1,0,0,0}, {0,1,1,1,1,0,0,0}, {0,2,2,2,1,0,0,0}, {1,3,3,3,3,2,1,1}, {2,3,3,3,3,2,2,2} }; // fine bit part for(x=0;x<8;x++){ for(y=0;y<8;y++){ ofs[x][y][0] = x/2; ofs[x][y][1] = y/2; ofs[x][y][2] = (x&1) + (y&1)*2; ofsR[y][x]=ofsRy[y]; ofsG[y][x]=ofsGx[x]; }} // repeat small image //block for(x=0;x<8;x++){ for(y=0;y<8;y++){ int r0 =ofsR[x][y]; int g0 =ofsG[x][y]; int b0 =ofsB[x][y]; int xx,yy; for(xx=0;xx<L/8;xx++){ for(yy=0;yy<L/8;yy++){ int ad0 = (xx+yy*(L/8))*3; int r=(pbuf[ad0 +0]/vv)*4 +r0; int g=(pbuf[ad0 +1]/vv)*4 +g0; int b=(pbuf[ad0 +2]/vv)*4 +b0; int x0=x+xx*8; int y0=y+yy*8; int adr=XY2ADR(x0,y0); colr[adr]=r; colg[adr]=g; colb[adr]=b; }} }} free(pbuf); return; } printf("#Couldn't load %s\n",fn); exit(1); } int ncol; #define RTMAX 128 int rt[RTMAX],gt[RTMAX],bt[RTMAX]; void reg_col_aux(int r, int g, int b) { int oo=r|g|b; if (oo&(~CBMASK)) return; if(cidx0[rgb2idx(r,g,b)]== 0) { rt[ncol]=r; gt[ncol]=g; bt[ncol]=b; ncol++; } } void reg_col(int ad, int flag) { if(solid[ad]!=1)return; int r=colr[ad]; int g=colg[ad]; int b=colb[ad]; if(flag==1) { reg_col_aux(r-1,g,b); reg_col_aux(r+1,g,b); reg_col_aux(r,g-1,b); reg_col_aux(r,g+1,b); reg_col_aux(r,g,b-1); reg_col_aux(r,g,b+1); } if(flag==2) { reg_col_aux(r-1,g-1,b); reg_col_aux(r-1,g+1,b); reg_col_aux(r+1,g-1,b); reg_col_aux(r+1,g+1,b); reg_col_aux(r,g-1,b-1); reg_col_aux(r,g-1,b+1); reg_col_aux(r,g+1,b-1); reg_col_aux(r,g+1,b+1); reg_col_aux(r-1,g,b-1); reg_col_aux(r-1,g,b+1); reg_col_aux(r+1,g,b-1); reg_col_aux(r+1,g,b+1); } if(flag==3) { reg_col_aux(r-1,g-1,b-1); reg_col_aux(r-1,g-1,b+1); reg_col_aux(r-1,g+1,b-1); reg_col_aux(r-1,g+1,b+1); reg_col_aux(r+1,g-1,b-1); reg_col_aux(r+1,g-1,b+1); reg_col_aux(r+1,g+1,b-1); reg_col_aux(r+1,g+1,b+1); } if(flag==4) { reg_col_aux(r-2,g,b); reg_col_aux(r+2,g,b); reg_col_aux(r,g-2,b); reg_col_aux(r,g+2,b); reg_col_aux(r,g,b+2); reg_col_aux(r,g,b-2); } } void reg_col0(int xx, int yy) { ncol=0; int x1=(xx-1)&LMASK; int x2=(xx+1)&LMASK; int y1=(yy-1)&LMASK; int y2=(yy+1)&LMASK; int ad1=XY2ADR(x1,yy); int ad2=XY2ADR(x2,yy); int ad3=XY2ADR(xx,y1); int ad4=XY2ADR(xx,y2); reg_col(ad1,1); reg_col(ad2,1); reg_col(ad3,1); reg_col(ad4,1); if(ncol!=0)return; reg_col(ad1,2); reg_col(ad2,2); reg_col(ad3,2); reg_col(ad4,2); if(ncol!=0)return; reg_col(ad1,3); reg_col(ad2,3); reg_col(ad3,3); reg_col(ad4,3); if(ncol!=0)return; reg_col(ad1,4); reg_col(ad2,4); reg_col(ad3,4); reg_col(ad4,4); } int place_one() { static int avmin=0; int ox=L/2- dwid/2; int oy=L/2- dwid/2; int x=0; int y=0; if(dwid==L) { x=(rand()>>4)&(L-1); y=(rand()>>4)&(L-1); } const int dx[4]={-1,1,0,0}; const int dy[4]={0,0,-1,1}; int cnt=0; #define CMAX 10000 #define RSHIFT 8 while(1) { int r1=rand()>>RSHIFT; int r2=RAND_MAX>>RSHIFT; while(1) { int xx=ox+x; int yy=oy+y; int ad=XY2ADR(xx,yy); if(solid[ad]==2)break; if((r2&3)!=3) { r1=rand()>>RSHIFT; r2=RAND_MAX>>RSHIFT; } int rnd=r1&3; r1>>=2; r2>>=2; x =(x+dx[rnd])&(dwid-1); y =(y+dy[rnd])&(dwid-1); } ncol=0; int xx=ox+x; int yy=oy+y; reg_col0(xx,yy); if(ncol!=0)break; cnt++; if(cnt==CMAX) break; if (1){ int rnd=(rand()>>10)&3; x =(x+dx[rnd])&(dwid-1); y =(y+dy[rnd])&(dwid-1); //printf("Fail %d\n",cnt); } } if(ncol==0) { //Check avail colors int ncol=0; int i; for(i=0;i<L2;i++) { if (solid[i]!=2)continue; int xx,yy; ADR2XY(i,xx,yy); reg_col0(xx,yy); if(ncol!=0) { int cc=(rand()>>4)%ncol; place_solid(xx,yy, rt[cc],gt[cc],bt[cc],2); return 0; } }//i return 1; } else { int cc=(rand()>>4)%ncol; place_solid(ox+x,oy+y, rt[cc],gt[cc],bt[cc],2); } int wx=abs(x-dwid/2); int wy=abs(y-dwid/2); if((wx>dwid/2-2 || wy>dwid/2-2) && (dwid!=L)) { dwid*=2; printf("Now wid=%d\n",dwid); dump(2, colr,colg,colb); } return 0; } int main(int argc, char **argv) { int i; //test address for(i=0;i<L2;i++) { int x,y,a2; ADR2XY(i,x,y); a2=XY2ADR(x,y); if(i!=a2)exit(1); } int ni=atoi(argv[1]); if(ni==0) { printf("Usage: a.out N.of.Seeds\n"); exit(1); } init_emp(); int np=init_misc(ni,0.5); #if 1 // Do DLA int t0=getmsec(); for(i=0;i<L2-ni - np;i++) { int ii=place_one(); if(i%1000==0) { int tt=getmsec(); printf("%d/%d %d %d sec\n",i,L2, i*100/(L2-ni-np), tt-t0); if(tt-t0>1000*60) { dump(4, colr,colg,colb); //exit(1); t0=tt; } int j; } if(ii!=0)break; }//loop #endif printf("Place %d Reserve %d\n",ni,np); //reorder avail col int nc=0; int mm; for(mm=0;mm<=VMAX*3;mm++) { int r,g,b; #if 1 for(r=0;r<=mm;r++){ if(r>=VMAX)continue; for(g=0;g<=mm-r;g++){ if(g>=VMAX)continue; b=mm-r-g; if(b>=VMAX)continue; int c=rgb2idx(r,g,b); if(cidx[c] < 0) emp_c[nc++]=c; }} #else //V for(g=0;g<=mm;g++) for(b=0;b<=mm;b++) emp_c[nc++]=rgb2idx(mm,g,b); for(r=0;r<=mm-1;r++) for(b=0;b<=mm;b++) emp_c[nc++]=rgb2idx(r,mm,b); for(r=0;r<=mm-1;r++) for(g=0;g<=mm-1;g++) emp_c[nc++]=rgb2idx(r,g,mm); #endif } printf("Reserve %d\n",nc); char *revflag = (char *)malloc(L2); //revert for(i=0;i<L2;i++) { revflag[i]=0; if(cidx[i]==-2)cidx[i]=-1; } for(i=0;i<L2;i++) { if(cidx[i]>=0) { int r,g,b; IDX2RGB(i,r,g,b); int ad=cidx[i]; revflag[ad]=1; colr[ad]=CBMASK-colr[ad]; colg[ad]=CBMASK-colg[ad]; colb[ad]=CBMASK-colb[ad]; } } int th= (int)(RAND_MAX*0.0); /////////////////////////////////// //Fill nc=0; int fl0=2; int cnt=0; int done=0; // Fill while(1) { cnt++; if(cnt==10)break; if(cnt%1000==0) dump(4, colr,colg,colb); int nfil=0; int fl2=fl0+1; if(fl2==256)fl2=2; //printf("fl=%d fl2=%d\n",fl0,fl2); int skip=0; for(i=0;i<L2;i++) { if(solid[i]!=fl0)continue; #if 0 if(rand()<th) {solid[i]=fl2; nfil++;continue;} ncol=0; int xx,yy; ADR2XY(i,xx,yy); reg_col0(xx,yy); if(ncol==0) {skip++; continue;} nfil++; int cc=(rand()>>4)%ncol; place_solid(xx,yy, rt[cc],gt[cc],bt[cc],fl2); #else int c=emp_c[nc];nc++; int r,g,b; IDX2RGB(c,r,g,b); int x,y; ADR2XY(i,x,y); place_solid(x,y, r,g,b, fl2); nfil++; #endif }//i //printf("%d placed 1\n",nfil); if(skip==0) { fl0=fl2; if(nfil==0) { done=1; break; } continue; } nfil=0; for(i=0;i<L2;i++) { if(solid[i]!=fl0)continue; while(cidx[emp_c[nc]]>=0)nc++; int r,g,b; IDX2RGB(emp_c[nc],r,g,b); int x,y; ADR2XY(i,x,y); place_solid(x,y, r,g,b, fl2); nfil++; } printf("%d/%d placed 2\n",nfil,skip); if(nfil==0) { done=1; break; } fl0=fl2; }// if(done==0) { for(i=0;i<L2;i++) { if(solid[i]==1)continue; int c=emp_c[nc];nc++; int r,g,b; IDX2RGB(c,r,g,b); int x,y; ADR2XY(i,x,y); place_solid(x,y, r,g,b, 2); }//i } //revert for(i=0;i<L2;i++) { if(revflag[i]==1) { int r,g,b; colr[i]=CBMASK-colr[i]; colg[i]=CBMASK-colg[i]; colb[i]=CBMASK-colb[i]; } } dump(4, colr,colg,colb); }
