draw7.c
0000/**********************************
0001
0002 PixMap
0003
0004**********************************/
0005
0006#include <stdlib.h>
0007#include "draw7.h"
0008#include <X11/Xlib.h>
0009#define MRGB 300
0010
0011/*****************************************
0012
0013 type of PixMap
0014 0 : 1-bit B&W (0=black, 1=white)
0015 1 : 4-bit grayscale
0016 2 : 8-bit grayscale
0017 3 : 16-bit color
0018 4 : 24-bit color
0019 5 : reserved (32-bit color?)
0020 6 : 2-bit indexed
0021 7 : 4-bit indexed
0022 8 : 8-bit indexed (non-standard color table)
0023 9 : 8-bit indexed (standard color table)
0024
0025 color in color table
0026 RGB 24 bit
0027
0028 a row of indices rounded to the byte boundary
0029
0030*******************************************/
0031
0032PixMap *pcreate(int type,int wid,int hei)
0033{
0034 PixMap *p;
0035 size_t size;
0036 int rowbytes,idxlen;
0037 unsigned char *chunk;
0038 int i,j,k,l,step,red,green,blue;
0039
0040 idxlen=0;
0041 switch(type){
0042 case 0: /* 1-bit B&W (0=black, 1=white) */
0043 rowbytes=wid/8+((wid%8) ? 1 : 0);
0044 idxlen=3*2;
0045 break;
0046 case 1: /* 4-bit grayscale */
0047 rowbytes=wid/2+((wid%2) ? 1 : 0);
0048 idxlen=3*16;
0049 break;
0050 case 2: /* 8-bit grayscale */
0051 rowbytes=wid;
0052 break;
0053 case 3: /* 16-bit color */
0054 rowbytes=2*wid;
0055 break;
0056 case 4: /* 24-bit color */
0057 rowbytes=3*wid;
0058 break;
0059 case 5: /* reserved (32-bit color) */
0060 rowbytes=4*wid;
0061 break;
0062 case 6: /* 2-bit indexed */
0063 rowbytes=wid/4+((wid%4) ? 1 : 0);
0064 idxlen=3*4;
0065 break;
0066 case 7: /* 4-bit indexed */
0067 rowbytes=wid/2+((wid%2) ? 1 : 0);
0068 idxlen=3*16;
0069 break;
0070 case 8: /* 8-bit indexed (non-standard color table) */
0071 case 9: /* 8-bit indexed (standard color table) */
0072 rowbytes=wid;
0073 idxlen=3*256;
0074 break;
0075 default:
0076 break;
0077 }
0078 size=9*sizeof(int)+sizeof(char *)+idxlen*sizeof(char)+rowbytes*hei*sizeof(char);
0079 p=(PixMap *)malloc(size);
0080 p->size=size;
0081 p->type=type;
0082 p->wid=wid;
0083 p->hei=hei;
0084 p->refx=0;
0085 p->refy=0;
0086 p->refz=0;
0087 p->rowbytes=rowbytes;
0088 p->idxlen=idxlen; /* index color table in the first part of data[] */
0089 p->pixdata=(unsigned char *)((char *)&(p->data[0])+idxlen); /* beginning of pixel data in the second part of data[] */
0090 if(type==0){ /* black white */
0091 chunk=(unsigned char *)&p->data[0];
0092 chunk[0]=chunk[1]=chunk[2]=0;
0093 chunk[3]=chunk[4]=chunk[5]=0xFF;
0094 }
0095 if(type==1){ /* 4bit gray */
0096 chunk=(unsigned char *)&p->data[0];
0097 l=0;
0098 for(i=0;i<16;i++){
0099 j=17*i;
0100 chunk[l++]=j;
0101 chunk[l++]=j;
0102 chunk[l++]=j;
0103 }
0104 }
0105 if(type==4){
0106 j=hei*rowbytes;
0107 for(i=0;i<j;i++) p->pixdata[i]=0xff;
0108 }
0109 if(type==5){
0110 j=wid*hei;
0111 for(i=0;i<j;i++) *((int *)(p->pixdata)+i)=0xffffffff;
0112 }
0113 if(type==6){ /* black, white, red, blue */
0114 chunk=(unsigned char *)&p->data[0];
0115 for(i=0;i<11;i++) chunk[i]=0;
0116 chunk[3]=chunk[4]=chunk[5]=chunk[6]=chunk[11]=0xFF;
0117 }
0118 if(type==7){ /* 14 colors */
0119 chunk=(unsigned char *)&p->data[0];
0120 for(i=0;i<21;i++) chunk[i]=0;
0121 chunk[3]=chunk[4]=chunk[6]=chunk[8]=chunk[13]=chunk[14]=0x7f;
0122 chunk[9]=chunk[16]=chunk[20]=0xff;
0123 for(i=0;i<21;i+=3)
0124 for(j=0;j<3;j++){
0125 if(chunk[i+j]==0) chunk[45-i+j]=0xff;
0126 else if(chunk[i+j]==0xff) chunk[45-i+j]=0;
0127 else chunk[45-i+j]=chunk[i+j];
0128 }
0129 }
0130 if(type==9){
0131 chunk=(unsigned char *)&p->data[0];
0132 l=0;
0133 step=0xFFFF/5;
0134 for(i=5;i>=0;i--){
0135 red=i*step;
0136 for(j=5;j>=0;j--){
0137 green=j*step;
0138 for(k=5;k>=0;k--){
0139 blue=k*step;
0140 if(i!=0||j!=0||k!=0){
0141 chunk[l++]=red;
0142 chunk[l++]=green;
0143 chunk[l++]=blue;
0144 }
0145 }
0146 }
0147 }
0148 step=0xFFFF/15;
0149 green=0;
0150 blue=0;
0151 for(i=14;i>0;i--){
0152 if(i%3!=0){
0153 red=i*step;
0154 chunk[l++]=red;
0155 chunk[l++]=green;
0156 chunk[l++]=blue;
0157 }
0158 }
0159 red=0;
0160 blue=0;
0161 for(i=14;i>0;i--){
0162 if(i%3!=0){
0163 green=i*step;
0164 chunk[l++]=red;
0165 chunk[l++]=green;
0166 chunk[l++]=blue;
0167 }
0168 }
0169 red=0;
0170 green=0;
0171 for(i=14;i>0;i--){
0172 if(i%3!=0){
0173 blue=i*step;
0174 chunk[l++]=red;
0175 chunk[l++]=green;
0176 chunk[l++]=blue;
0177 }
0178 }
0179 for(i=14;i>0;i--){
0180 if(i%3!=0){
0181 red=green=blue=i*step;
0182 chunk[l++]=red;
0183 chunk[l++]=green;
0184 chunk[l++]=blue;
0185 }
0186 }
0187 red=0;
0188 green=0;
0189 blue=0;
0190 chunk[l++]=red;
0191 chunk[l++]=green;
0192 chunk[l++]=blue;
0193 }
0194 return p;
0195}
0196
0197int pdestroy(PixMap *p)
0198{
0199 free(p);
0200 return 0;
0201}
0202
0203/******************************************************
0204 r,g,b - 0 to 255
0205******************************************************/
0206int putpix(PixMap *p,int x,int y,int r,int g,int b)
0207{
0208 int i,j,k,l;
0209 unsigned short s1,s2,s3;
0210 unsigned char c1,c2,c3;
0211 unsigned char *cp;
0212
0213 if(x<0||x>=p->wid) return 0;
0214 if(y<0||y>=p->hei) return 0;
0215
0216 switch(p->type){
0217 case 0: /* 1-bit B&W (0=black, 1=white) */
0218 i=p->rowbytes*y+x/8;
0219 c2=*((unsigned char*)p->pixdata+i);
0220 j=x%8;
0221 if(r==0){ /* black */
0222 c1=1;
0223 c1<<=j;
0224 c2&=~c1;
0225 }
0226 else{
0227 c1=1;
0228 c1<<=j;
0229 c2|=c1;
0230 }
0231 *((unsigned char*)p->pixdata+i)=c2;
0232 break;
0233 case 1: /* 4-bit grayscale */
0234 i=p->rowbytes*y+x/2;
0235 c2=*((unsigned char*)p->pixdata+i);
0236 j=x%2;
0237 c1=r;
0238 if(j==0){ /* replace lsb */
0239 c1>>=4;
0240 c2&=0xf0;
0241 c2|=c1;
0242 }
0243 else{
0244 c1&=0xf0;
0245 c2&=0xf;
0246 c2|=c1;
0247 }
0248 *((unsigned char*)p->pixdata+i)=c2;
0249 break;
0250 case 2: /* 8-bit grayscale */
0251 i=p->rowbytes*y+x;
0252 *((unsigned char*)p->pixdata+i)=r;
0253 break;
0254 case 3: /* 16-bit color */
0255 s1=0x0000;
0256 s2=r;
0257 s2<<=8;
0258 s2&=0xf800;
0259 s1|=s2;
0260 s2=g;
0261 s2<<=3;
0262 s2&=0x7c0;
0263 s1|=s2;
0264 s2=b;
0265 s2>>3;
0266 s2&=0x1f;
0267 s1|=s2;
0268 i=p->rowbytes*y+2*x;
0269 *(unsigned short*)((unsigned char*)p->pixdata+i)=s1;
0270 break;
0271 case 4: /* 24-bit color */
0272 i=p->rowbytes*y+3*x;
0273 *((unsigned char*)p->pixdata+i)=r;
0274 *((unsigned char*)p->pixdata+i+1)=g;
0275 *((unsigned char*)p->pixdata+i+2)=b;
0276 break;
0277 case 5: /* reserved (32-bit color?) */
0278 break;
0279 case 6: /* 2-bit indexed */
0280 k=10000;
0281 cp=(unsigned char*)&p->data[0];
0282 for(i=0;i<4;i++){
0283 c1=*(cp+i*3);
0284 c2=*(cp+i*3+1);
0285 c3=*(cp+i*3+2);
0286 if(c1>r) l=c1-r;
0287 else l=r-c1;
0288 if(c2>g) l+=c2-g;
0289 else l+=g-c2;
0290 if(c3>b) l+=c3-b;
0291 else l+=b-c3;
0292 if(l<k){
0293 k=l;
0294 j=i;
0295 }
0296 }
0297 i=p->rowbytes*y+x/4;
0298 c2=*((unsigned char*)p->pixdata+i);
0299 k=x%4;
0300 c1=0x3<<(k*2);
0301 c1=~c1;
0302 c2&=c1;
0303 c1=j;
0304 c1<<=k*2;
0305 c2|=c1;
0306 *((unsigned char*)p->pixdata+i)=c2;
0307 break;
0308 case 7: /* 4-bit indexed */
0309 k=10000;
0310 cp=(unsigned char*)&p->data[0];
0311 for(i=0;i<16;i++){
0312 c1=*(cp+i*3);
0313 c2=*(cp+i*3+1);
0314 c3=*(cp+i*3+2);
0315 if(c1>r) l=c1-r;
0316 else l=r-c1;
0317 if(c2>g) l+=c2-g;
0318 else l+=g-c2;
0319 if(c3>b) l+=c3-b;
0320 else l+=b-c3;
0321 if(l<k){
0322 k=l;
0323 j=i;
0324 }
0325 }
0326 i=p->rowbytes*y+x/2;
0327 c2=*((unsigned char*)p->pixdata+i);
0328 k=x%2;
0329 if(k==0){
0330 c2&=0xf0;
0331 c1=j;
0332 }
0333 else{
0334 c2&=0xf;
0335 c1=j;
0336 c1<<=4;
0337 }
0338 c2|=c1;
0339 *((unsigned char*)p->pixdata+i)=c2;
0340 break;
0341 case 8: /* 8-bit indexed (non-standard color table) */
0342 k=10000;
0343 cp=(unsigned char*)&p->data[0];
0344 for(i=0;i<256;i++){
0345 c1=*(cp+i*3);
0346 c2=*(cp+i*3+1);
0347 c3=*(cp+i*3+2);
0348 if(c1>r) l=c1-r;
0349 else l=r-c1;
0350 if(c2>g) l+=c2-g;
0351 else l+=g-c2;
0352 if(c3>b) l+=c3-b;
0353 else l+=b-c3;
0354 if(l<k){
0355 k=l;
0356 j=i;
0357 }
0358 }
0359 i=p->rowbytes*y+x;
0360 *((unsigned char*)p->pixdata+i)=j;
0361 break;
0362 case 9: /* 8-bit indexed (standard color table) */
0363 i=p->rowbytes*y+x;
0364 *((unsigned char*)p->pixdata+i)=StdColor1(r,g,b);
0365 break;
0366 default:
0367 break;
0368 }
0369 return 0;
0370}
0371
0372/** 16-bit color **/
0373int putpix16(PixMap *p,int x,int y,int l)
0374{
0375 int i;
0376 i=p->rowbytes*y+2*x;
0377 *(unsigned short*)((unsigned char*)p->pixdata+i)=l;
0378 return 0;
0379}
0380
0381int putpix32(PixMap *p,int x,int y,int l)
0382{
0383 int i;
0384 i=p->wid*y+x;
0385 *((int *)p->pixdata+i)=l;
0386 return 0;
0387}
0388
0389int putpixid(PixMap *p,int x,int y,int idx)
0390{
0391 int i,j,k,l;
0392 unsigned short s1,s2,s3;
0393 unsigned char c1,c2,c3;
0394 unsigned char *cp;
0395
0396 if(x<0||x>=p->wid) return 0;
0397 if(y<0||y>=p->hei) return 0;
0398
0399 switch(p->type){
0400 case 0: /* 1-bit B&W (0=black, 1=white) */
0401 i=p->rowbytes*y+x/8;
0402 c2=*((unsigned char*)p->pixdata+i);
0403 j=x%8;
0404 if(idx==0){ /* black */
0405 c1=1;
0406 c1<<=j;
0407 c2&=~c1;
0408 }
0409 else{
0410 c1=1;
0411 c1<<=j;
0412 c2|=c1;
0413 }
0414 *((unsigned char*)p->pixdata+i)=c2;
0415 break;
0416 case 1: /* 4-bit grayscale */
0417 i=p->rowbytes*y+x/2;
0418 c2=*((unsigned char*)p->pixdata+i);
0419 j=x%2;
0420 c1=idx;
0421 if(j==0){ /* replace lsb */
0422 c2&=0xf0;
0423 c2|=c1;
0424 }
0425 else{
0426 c1<<=4;
0427 c2&=0xf;
0428 c2|=c1;
0429 }
0430 *((unsigned char*)p->pixdata+i)=c2;
0431 break;
0432 case 2: /* 8-bit grayscale */
0433 i=p->rowbytes*y+x;
0434 *((unsigned char*)p->pixdata+i)=idx;
0435 break;
0436 case 6: /* 2-bit indexed */
0437 i=p->rowbytes*y+x/4;
0438 c2=*((unsigned char*)p->pixdata+i);
0439 k=x%4;
0440 c1=0x3<<(k*2);
0441 c1=~c1;
0442 c2&=c1;
0443 c1=idx;
0444 c1<<=k*2;
0445 c2|=c1;
0446 *((unsigned char*)p->pixdata+i)=c2;
0447 break;
0448 case 7: /* 4-bit indexed */
0449 i=p->rowbytes*y+x/2;
0450 c2=*((unsigned char*)p->pixdata+i);
0451 k=x%2;
0452 if(k==0){
0453 c2&=0xf0;
0454 c1=idx;
0455 }
0456 else{
0457 c2&=0xf;
0458 c1=idx;
0459 c1<<=4;
0460 }
0461 c2|=c1;
0462 *((unsigned char*)p->pixdata+i)=c2;
0463 break;
0464 case 8: /* 8-bit indexed (non-standard color table) */
0465 i=p->rowbytes*y+x;
0466 *((unsigned char*)p->pixdata+i)=idx;
0467 break;
0468 case 9: /* 8-bit indexed (standard color table) */
0469 i=p->rowbytes*y+x;
0470 *((unsigned char*)p->pixdata+i)=idx;
0471 break;
0472 default:
0473 break;
0474 }
0475 return 0;
0476}
0477
0478
0479
0480/*******************************************************
0481 r,g,b - 0 to 255
0482*******************************************************/
0483int getpix(PixMap *p,int x,int y,int *r,int *g,int *b)
0484{
0485 int i,j,k,l;
0486 unsigned short s1,s2,s3;
0487 unsigned char c1,c2,c3;
0488 unsigned char *cp;
0489
0490 if(x<0||x>=p->wid) return 0;
0491 if(y<0||y>=p->hei) return 0;
0492
0493 switch(p->type){
0494 case 0: /* 1-bit B&W (0=black, 1=white) */
0495 i=p->rowbytes*y+x/8;
0496 c2=*((unsigned char*)p->pixdata+i);
0497 j=x%8;
0498 c1=1;
0499 c1<<=j;
0500 if(c2&c1){
0501 *r=255;
0502 *g=255;
0503 *b=255;
0504 }
0505 else{
0506 *r=0;
0507 *g=0;
0508 *b=0;
0509 }
0510 break;
0511 case 1: /* 4-bit grayscale */
0512 i=p->rowbytes*y+x/2;
0513 c2=*((unsigned char*)p->pixdata+i);
0514 j=x%2;
0515 if(j==0) c2<<=4;
0516 else c2&=0xf0;
0517 *r=c2;
0518 *g=c2;
0519 *b=c2;
0520 break;
0521 case 2: /* 8-bit grayscale */
0522 i=p->rowbytes*y+x;
0523 c2=*((unsigned char*)p->pixdata+i);
0524 *r=c2;
0525 *g=c2;
0526 *b=c2;
0527 break;
0528 case 3: /* 16-bit color */
0529 i=p->rowbytes*y+2*x;
0530 s1=*(unsigned short*)((unsigned char*)p->pixdata+i);
0531 c1=(s1>>11)&0x1f;
0532 c1<<=3;
0533 c2=(s1>>5)&0x3f;
0534 c2<<=2;
0535 c3=s1&0x1f;
0536 c3<<=3;
0537 *r=c1;
0538 *g=c2;
0539 *b=c3;
0540 break;
0541 case 4: /* 24-bit color */
0542 i=p->rowbytes*y+3*x;
0543 *r=*((unsigned char*)p->pixdata+i);
0544 *g=*((unsigned char*)p->pixdata+i+1);
0545 *b=*((unsigned char*)p->pixdata+i+2);
0546 break;
0547 case 5: /* reserved (32-bit color?) */
0548 break;
0549 case 6: /* 2-bit indexed */
0550 i=p->rowbytes*y+x/4;
0551 c2=*((unsigned char*)p->pixdata+i);
0552 k=x%4;
0553 c2>>=(k*2);
0554 c2&=3;
0555 cp=(unsigned char*)&p->data[0];
0556 *r=*(cp+c2*3);
0557 *g=*(cp+c2*3+1);
0558 *b=*(cp+c2*3+2);
0559 break;
0560 case 7: /* 4-bit indexed */
0561 i=p->rowbytes*y+x/2;
0562 c2=*((unsigned char*)p->pixdata+i);
0563 k=x%2;
0564 if(k==1) c2>>=4;
0565 c2&=0xf;
0566 cp=(unsigned char*)&p->data[0];
0567 *r=*(cp+c2*3);
0568 *g=*(cp+c2*3+1);
0569 *b=*(cp+c2*3+2);
0570 break;
0571 case 8: /* 8-bit indexed (non-standard color table) */
0572 case 9: /* 8-bit indexed (standard color table) */
0573 i=p->rowbytes*y+x;
0574 c2=*((unsigned char*)p->pixdata+i);
0575 cp=(unsigned char*)&p->data[0];
0576 *r=*(cp+c2*3);
0577 *g=*(cp+c2*3+1);
0578 *b=*(cp+c2*3+2);
0579 break;
0580 default:
0581 break;
0582 }
0583 return 0;
0584}
0585
0586int getpix32(PixMap *p,int x,int y)
0587{
0588 int i;
0589 i=p->wid*y+x;
0590 return *((int *)p->pixdata+i);
0591}
0592
0593int getpixid(PixMap *p,int x,int y)
0594{
0595 int i,j,k,l;
0596 unsigned short s1,s2,s3;
0597 unsigned char c1,c2,c3;
0598 unsigned char *cp;
0599
0600 if(x<0||x>=p->wid) return 0;
0601 if(y<0||y>=p->hei) return 0;
0602
0603 switch(p->type){
0604 case 0: /* 1-bit B&W (0=black, 1=white) */
0605 i=p->rowbytes*y+x/8;
0606 c2=*((unsigned char*)p->pixdata+i);
0607 j=x%8;
0608 c2>>=j;
0609 k=c2&1;
0610 break;
0611 case 1: /* 4-bit grayscale */
0612 case 7: /* 4-bit indexed */
0613 i=p->rowbytes*y+x/2;
0614 c2=*((unsigned char*)p->pixdata+i);
0615 j=x%2;
0616 c2>>=j*4;
0617 k=c2&0xf;
0618 break;
0619 case 2: /* 8-bit grayscale */
0620 case 8: /* 8-bit indexed (non-standard color table) */
0621 case 9: /* 8-bit indexed (standard color table) */
0622 i=p->rowbytes*y+x;
0623 k=*((unsigned char*)p->pixdata+i);
0624 break;
0625 case 6: /* 2-bit indexed */
0626 i=p->rowbytes*y+x/4;
0627 c2=*((unsigned char*)p->pixdata+i);
0628 j=x%4;
0629 c2>>=j*2;
0630 k=c2&0x3;
0631 break;
0632 default:
0633 k=0;
0634 break;
0635 }
0636 return k;
0637}
0638
0639int StdColor1(int r1,int g1,int b1)
0640{
0641 int i;
0642 unsigned int r,g,b;
0643
0644 r=r1*(0xffff/255);
0645 g=g1*(0xffff/255);
0646 b=b1*(0xffff/255);
0647
0648 if(r==0&&g==0&&b==0){
0649 return 255;
0650 }
0651 if(r==0xffff&&g==0xffff&&b==0xffff){
0652 return 0;
0653 }
0654 if(r==0&&g==0){
0655 i=(b+2185)/4369;
0656 if(i%3!=0){
0657 return 245-(i-i/3);
0658 }
0659 }
0660 if(g==0&&b==0){
0661 i=(r+2185)/4369;
0662 if(i%3!=0){
0663 return 225-(i-i/3);
0664 }
0665 }
0666 if(b==0&&r==0){
0667 i=(g+2185)/4369;
0668 if(i%3!=0){
0669 return 235-(i-i/3);
0670 }
0671 }
0672 if(b==g&&r==g){ // gray scale
0673 i=(g+2185)/4369;
0674 if(i!=0&&i%3!=0){
0675 return 255-(i-i/3);
0676 }
0677 }
0678 i=215-((r+6554)/13107)*36-((g+6554)/13107)*6-(b+6554)/13107;
0679 if(i==215) i=255;
0680 return i;
0681}
0682
0683/*****************************************************************************
0684 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
0685 0 0 r7g7b7r6g6b6r5g5b5r4g4b4r3g3b3r2g2b2r1g1b1r0b0g0<-aa-><-bb->
0686 <-aa-> number of bits from msb that matches the previous entry
0687 <-bb-> number of bits from msb that is effective - 1
0688
0689 octree : encode rgb value in int
0690*****************************************************************************/
0691int octree(unsigned char r,unsigned char g,unsigned char b)
0692{
0693 int i,j,k,l,m,n,o;
0694 i=7; /* effective bits 8 */
0695 j=r;
0696 k=g;
0697 l=b;
0698 m=1;
0699 for(o=0;o<8;o++){
0700 n=0;
0701 if(j&m) n|=4;
0702 if(k&m) n|=2;
0703 if(l&m) n|=1;
0704 n<<=6+o*3;
0705 i|=n;
0706 m<<=1;
0707 }
0708 return i;
0709}
0710
0711void unoctree(unsigned char *r,unsigned char *g,unsigned char *b,int o)
0712{
0713 int i,j,k,l,n;
0714 j=0; /* r */
0715 k=0; /* g */
0716 l=0; /* b */
0717 n=0x20000000;
0718 for(i=0;i<8;i++){
0719 j<<=1;
0720 if(o&n) j|=1;
0721 n>>=1;
0722 k<<=1;
0723 if(o&n) k|=1;
0724 n>>=1;
0725 l<<=1;
0726 if(o&n) l|=1;
0727 n>>=1;
0728 }
0729 *r=j;
0730 *g=k;
0731 *b=l;
0732}
0733
0734/***********************************************************************
0735 simila : similarity
0736 enter <-aa-> in *n
0737***********************************************************************/
0738int simila(int m,int *n)
0739{
0740 int i,j,k,l,o;
0741 i=m&7;
0742 j=*n&7;
0743 o=(i<j)? i:j;
0744 l=*n;
0745 k=0x38000000;
0746 for(i=0;i<o;i++){
0747 if((m&k)!=(l&k)) break;
0748 k>>=3;
0749 }
0750 i<<=3;
0751 j=0xffffffc7&l; /* clear <-a-> field */
0752 j|=i;
0753 *n=j;
0754 return 0;
0755}
0756
0757/**************************************************
0758 cnvtype : Convert PixMap
0759 s - source PixMap
0760 d - destination PixMap
0761 pref - preference for generating the color table
0762 0 : reduce darkest
0763 1 : reduce brightest
0764 2 : reduce sparse
0765 3 : reduce dense
0766**************************************************/
0767int cnvtype(PixMap *s,PixMap *d,int pref)
0768{
0769 int rgb[MRGB];
0770 int rgb1;
0771 int nrgb;
0772 int count[MRGB];
0773 unsigned char *ps;
0774 int i,j,k,l,m,n,o;
0775 int i1,i2,i3,i4,i5,i6;
0776 int j1,j2,j3;
0777 int mrgb=MRGB;
0778
0779 if(s->type!=4||d->type!=8) return 1;
0780 /** 24-bit to 8-bit-indexed **/
0781 ps=s->pixdata; /* source pix */
0782 n=s->wid*s->hei;
0783 m=n*3;
0784 nrgb=0;
0785 count[nrgb]=1;
0786 rgb[nrgb++]=octree(0,0,0); /* black */
0787 count[nrgb]=1;
0788 rgb[nrgb++]=octree((unsigned char)0xff,(unsigned char)0xff,(unsigned char)0xff); /* white */
0789 for(j1=0;j1<4;j1++){
0790 switch(j1){
0791 case 0:
0792 j2=0;
0793 j3=24;
0794 break;
0795 case 1:
0796 j2=12;
0797 j3=24;
0798 break;
0799 case 2:
0800 j2=6;
0801 j3=12;
0802 break;
0803 case 3:
0804 j2=3;
0805 j3=6;
0806 break;
0807 }
0808 for(i=j2;i<m;i+=j3){
0809 // for(i=0;i<m;i+=3){ /* do for each pixel */
0810 /*****************************************************************************
0811 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
0812 0 0 r7g7b7r6g6b6r5g5b5r4g4b4r3g3b3r2g2b2r1g1b1r0b0g0<-aa-><-bb->
0813 <-aa-> number of bits from msb that matches the previous entry
0814 <-bb-> number of bits from msb that is effective -1
0815 *****************************************************************************/
0816 rgb1=octree(ps[i],ps[i+1],ps[i+2]); /* 24-bit octree encoding */
0817 for(j=1;j<nrgb;j*=2); /* j is power of 2, and greater than nrgb-1 */
0818 for(l=j/2;;l/=2){
0819 if(j>=nrgb) k=-1;
0820 else{
0821 i1=rgb[j];
0822 i2=i1&7; /* effective msb's -1 */
0823 i3=~((1<<(6+(7-i2)*3))-1); /* mask */
0824 i4=rgb1&i3;
0825 i5=rgb[j]&i3;
0826 if(i4<i5) k=-1;
0827 else if(i4==i5) k=0;
0828 else k=1;
0829 }
0830 if(k==0) break; /* rgb1 is already in the list of indices */
0831 if(k==-1) j-=l; /* rgb1 was less than rgb[j] */
0832 else j+=l; /* rgb1 was larger than rgb[j] */
0833 if(l==0) break;
0834 } /* for */
0835 if(k==0) count[j]++;
0836 else{ /* insert */
0837 if(k==1) j++; /* now rgb[j] is greater than rgb1 */
0838 for(l=nrgb;l>j;l--){
0839 rgb[l]=rgb[l-1]; /* now rgb[j] is vacant */
0840 count[l]=count[l-1];
0841 }
0842 count[j]=1;
0843 rgb[j]=rgb1; /* insert */
0844 simila(rgb[j-1],&rgb[j]); /* similarity with the preceeding entry */
0845 simila(rgb[j],&rgb[j+1]);
0846 nrgb++;
0847 }
0848 if(nrgb==MRGB){ /* reduce */
0849 i2=0; /* similarity length */
0850 switch (pref){
0851 case 0: /* reduce darkest */
0852 for(j=1;j<nrgb;j++){
0853 i3=rgb[j]&0x38; /* bits that matches the previous entry times 8 */
0854 if(i3>i2){ /* darkest within longest match */
0855 i1=j;
0856 i2=i3; /* longest match bits */
0857 }
0858 }
0859 break;
0860 case 1: /* reduce brightest */
0861 for(j=1;j<nrgb;j++){
0862 i3=rgb[j]&0x38; /* bits that matches the previous entry times 8 */
0863 if(i3>=i2){ /* brightest within longest match */
0864 i1=j;
0865 i2=i3; /* longest match bits */
0866 }
0867 }
0868 for(j=i1;;j--){
0869 i3=rgb[j]&0x38; /* bits that matches the previous entry */
0870 if(i3!=i2) break; /* j,..,i1 have the same length i2 */
0871 }
0872 i1=j+1;
0873 break;
0874 case 2: /* reduce sparse */
0875 for(j=1;j<nrgb-1;j++){ /* nrgb-1 not to be reduced */
0876 i3=rgb[j]&0x38; /* bits that matches the previous entry times 8 */
0877 if(i3>i2){
0878 i2=i3; /* longest match bits */
0879 }
0880 }
0881 i4=0;
0882 i5=1000000;
0883 for(j=1;j<nrgb-1;j++){
0884 i3=rgb[j]&0x38; /* bits that matches the previous entry times 8 */
0885 if(i3==i2){
0886 if(i4==0){
0887 i1=j;
0888 i4=count[j-1];
0889 }
0890 i4+=count[j];
0891 }
0892 else{
0893 if(i4!=0){
0894 if(i4<i5){
0895 i5=i4;
0896 i6=i1;
0897 }
0898 i4=0;
0899 }
0900 }
0901 }
0902 if(i4!=0){
0903 if(i4<i5){
0904 i5=i4;
0905 i6=i1;
0906 }
0907 }
0908 i1=i6;
0909 break;
0910 case 3: /* reduce dense */
0911 for(j=1;j<nrgb;j++){
0912 i3=rgb[j]&0x38; /* bits that matches the previous entry times 8 */
0913 if(i3>i2){
0914 i2=i3; /* longest match bits */
0915 }
0916 }
0917 i4=0;
0918 i5=0;
0919 for(j=1;j<nrgb;j++){
0920 i3=rgb[j]&0x38; /* bits that matches the previous entry times 8 */
0921 if(i3==i2){
0922 if(i4==0){
0923 i1=j;
0924 i4=count[j-1];
0925 }
0926 i4+=count[j];
0927 }
0928 else{
0929 if(i4!=0){
0930 if(i4>i5){
0931 i5=i4;
0932 i6=i1;
0933 }
0934 }
0935 i4=0;
0936 }
0937 }
0938 i1=i6;
0939 break;
0940 default:
0941 break;
0942 }
0943 for(j=i1;j<nrgb-1;j++){
0944 i3=rgb[j]&0x38; /* bits that matches the previous entry */
0945 if(i3!=i2) break; /* i1-1,i1,..,j-1 have the same length i2 */
0946 }
0947 i2>>=3; /* 0 - 7 */
0948 i5=j-i1; /* items with the same length = j-i1+1 ( could be 2 - 8) , i5 could be 1 - 7 */
0949 i6=j;
0950 for(j=i1;j<i6;j++) count[i1-1]+=count[j];
0951 for(j=i6;j<nrgb;j++){
0952 rgb[j-i5]=rgb[j];
0953 count[j-i5]=count[j];
0954 }
0955 nrgb-=i5;
0956 /* now clear the bit i2+1 to end */
0957 i4=1;
0958 i4=(i4<<((8-i2)*3+6))-1; /* number-of-shift bits raised */
0959 i4=~i4;
0960 rgb[i1-1]&=i4;
0961 rgb[i1-1]|=i2-1;
0962 if(i1>1) simila(rgb[i1-2],&rgb[i1-1]); /* similarity with the preceeding entry */
0963 if(i1<nrgb) simila(rgb[i1-1],&rgb[i1]);
0964 }
0965 } /* for */
0966 }
0967 while(nrgb>256){
0968 i2=0; /* similarity length */
0969 switch (pref){
0970 case 0: /* reduce darkest */
0971 for(j=1;j<nrgb;j++){
0972 i3=rgb[j]&0x38; /* bits that matches the previous entry times 8 */
0973 if(i3>i2){ /* darkest within longest match */
0974 i1=j;
0975 i2=i3; /* longest match bits */
0976 }
0977 }
0978 break;
0979 case 1: /* reduce brightest */
0980 for(j=1;j<nrgb;j++){
0981 i3=rgb[j]&0x38; /* bits that matches the previous entry times 8 */
0982 if(i3>=i2){ /* brightest within longest match */
0983 i1=j;
0984 i2=i3; /* longest match bits */
0985 }
0986 }
0987 for(j=i1;;j--){
0988 i3=rgb[j]&0x38; /* bits that matches the previous entry */
0989 if(i3!=i2) break; /* j,..,i1 have the same length i2 */
0990 }
0991 i1=j+1;
0992 break;
0993 case 2: /* reduce sparse */
0994 for(j=1;j<nrgb-1;j++){
0995 i3=rgb[j]&0x38; /* bits that matches the previous entry times 8 */
0996 if(i3>i2){
0997 i2=i3; /* longest match bits */
0998 }
0999 }
1000 i4=0;
1001 i5=1000000;
1002 for(j=1;j<nrgb-1;j++){
1003 i3=rgb[j]&0x38; /* bits that matches the previous entry times 8 */
1004 if(i3==i2){
1005 if(i4==0){
1006 i1=j;
1007 i4=count[j-1];
1008 }
1009 i4+=count[j];
1010 }
1011 else{
1012 if(i4!=0){
1013 if(i4<i5){
1014 i5=i4;
1015 i6=i1;
1016 }
1017 i4=0;
1018 }
1019 }
1020 }
1021 if(i4!=0){
1022 if(i4<i5){
1023 i5=i4;
1024 i6=i1;
1025 }
1026 }
1027 i1=i6;
1028 break;
1029 case 3: /* reduce dense */
1030 for(j=1;j<nrgb;j++){
1031 i3=rgb[j]&0x38; /* bits that matches the previous entry times 8 */
1032 if(i3>i2){
1033 i2=i3; /* longest match bits */
1034 }
1035 }
1036 i4=0;
1037 i5=0;
1038 for(j=1;j<nrgb;j++){
1039 i3=rgb[j]&0x38; /* bits that matches the previous entry times 8 */
1040 if(i3==i2){
1041 if(i4==0){
1042 i1=j;
1043 i4=count[j-1];
1044 }
1045 i4+=count[j];
1046 }
1047 else{
1048 if(i4!=0){
1049 if(i4>i5){
1050 i5=i4;
1051 i6=i1;
1052 }
1053 }
1054 i4=0;
1055 }
1056 }
1057 i1=i6;
1058 break;
1059 default:
1060 break;
1061 }
1062 for(j=i1;j<nrgb-1;j++){
1063 i3=rgb[j]&0x38; /* bits that matches the previous entry */
1064 if(i3!=i2) break; /* i1-1,i1,..,j-1 have the same length i2 */
1065 }
1066 i2>>=3; /* 0 - 7 */
1067 i5=j-i1; /* items with the same length = j-i1+1 ( could be 2 - 8) , i5 could be 1 - 7 */
1068 i6=j;
1069 for(j=i1;j<i6;j++) count[i1-1]+=count[j];
1070 for(j=i6;j<nrgb;j++){
1071 rgb[j-i5]=rgb[j];
1072 count[j-i5]=count[j];
1073 }
1074 nrgb-=i5;
1075 /* now clear the bit i2+1 to end */
1076 i4=1;
1077 i4=(i4<<((8-i2)*3+6))-1; /* number-of-shift bits raised */
1078 i4=~i4;
1079 rgb[i1-1]&=i4;
1080 rgb[i1-1]|=i2-1;
1081 if(i1>1) simila(rgb[i1-2],&rgb[i1-1]); /* similarity with the preceeding entry */
1082 if(i1<nrgb) simila(rgb[i1-1],&rgb[i1]);
1083 }
1084 for(i=0;i<nrgb;i++){
1085 j=3*i;
1086 unoctree((unsigned char*)&d->data[j],(unsigned char*)&d->data[j+1],(unsigned char*)&d->data[j+2],rgb[i]);
1087 }
1088 for(;i<256;i++){ /* nrgb can be less than 256 */
1089 j=3*i;
1090 d->data[j]=d->data[j-3];
1091 d->data[j+1]=d->data[j-2];
1092 d->data[j+2]=d->data[j-1];
1093 }
1094 for(o=1;o<nrgb;o*=2); /* o is factorial of 2, and greater than nrgb-1 */
1095 for(i=0;i<m;i+=3){ /* do for each pixel */
1096 rgb1=octree(ps[i],ps[i+1],ps[i+2]); /* 24-bit octree encoding */
1097 j=o;
1098 for(l=j/2;;l/=2){
1099 if(j>=nrgb) k=-1;
1100 else{
1101 i1=rgb[j];
1102 i2=i1&7; /* effective msb's -1 */
1103 i3=~((1<<(6+(7-i2)*3))-1); /* mask */
1104 i4=rgb1&i3;
1105 i5=rgb[j]&i3;
1106 if(i4<i5) k=-1;
1107 else if(i4==i5) k=0;
1108 else k=1;
1109 }
1110 if(k==0) break; /* rgb1 is already in the list of indices */
1111 if(k==-1) j-=l; /* rgb1 was less than rgb[j] */
1112 else j+=l; /* rgb1 was larger than rgb[j] */
1113 if(l==0) break;
1114 } /* for */
1115 d->pixdata[i/3]=j;
1116 } /* for */
1117 return 0;
1118}
1119