home *** CD-ROM | disk | FTP | other *** search
/ FM Towns: Free Software Collection 9 / FM Towns Free Software Collection 9.iso / t_os / tool / gara2 / spp / src / optimize.c next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  6.0 KB  |  348 lines
  1. /* アルゴリズム－２ */
  2.  
  3. #include    <stdio.h>
  4. #include    <malloc.h>
  5. #include    <mos.h>
  6. #include    <s_button.h>
  7.  
  8. /* 関数のプロトタイプ宣言(なんかポインタの表現が変だけど(^^;)) */
  9. int        SOP_selPal(short *pal,short col[],int dotnum,int level);
  10. int        SOP_optimize(char *pat,short pal[16],short *buf,int dotnum);
  11. void     SOP_qsort    (short a[],int left,int right);
  12. void    SPM_MC_tokei();
  13. void    SPM_MC_fude();
  14. void    SPM_MC_ya();
  15. static    void SOP_qsort2    (short a[],short b[],int left,int right);
  16.  
  17.  
  18. /* 構造体の定義 */
  19. typedef struct
  20. {
  21.     int        r,g,b;
  22. } RGB;                    /* そのものずばり！ */
  23.  
  24.  
  25.  
  26.  
  27. /* マクロ */
  28. #define        US        unsigned
  29. #define        _SQ(x)    ((x)*(x))    /* 自乗 */
  30. #define        _DIFF(a,b) ((a)>(b)) ? ((a)-(b)) : ((b)-(a))    /* 差 */
  31. #define        _DIST(a,b) _SQ(_R(a)-_R(b))*900 + _SQ(_G(a)-_G(b))*3364 + _SQ(_B(a)-_B(b))*144    /* 色空間における距離の自乗 */
  32. #define        _DISTC(r1,g1,b1,r2,g2,b2)    _SQ(r1-r2)*900 + _SQ(g1-g2)*3364 + _SQ(b1-b2)*144    /* 色空間における距離の自乗(rgbで入力) */
  33.  
  34.  
  35.  
  36.  
  37.  
  38.  
  39. /* グローバル変数の定義 */
  40.  
  41. extern    char    mpwork[258];
  42.  
  43.  
  44.  
  45.  
  46. /*
  47. short    coldat[20]={200,300,100,200,300,
  48.         1000,201,200,300,400,
  49.         12,201,3003,20,99,
  50.         109,209,222,100,900};
  51.  
  52. short    coldat[20]={1,1,3,3,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
  53. */
  54.  
  55.  
  56. static void    debug(short *pt,int n)
  57. {
  58.     int        i;
  59.     for (i=0;i<n;i++)
  60.         printf("%d\t",pt[i]);
  61.     return;
  62. }
  63.  
  64.  
  65. /* マウスカーソルを時計にする */
  66. void    SPM_MC_tokei()
  67. {
  68.     MOS_disp(0);
  69.     MOS_typeRom(116,0,0,mpwork);
  70.     MOS_disp(1);
  71.     return;
  72. }
  73.  
  74. /* マウスカーソルを矢印に */
  75. void    SPM_MC_ya()
  76. {
  77.     MOS_disp(0);
  78.     MOS_typeRom(81,0,0,mpwork);
  79.     MOS_disp(1);
  80.     return;
  81. }
  82.  
  83. /* マウスカーソルを筆にする */
  84. void    SPM_MC_fude()
  85. {
  86.     MOS_disp(0);
  87.     MOS_typeRom(113,0,0,mpwork);
  88.     MOS_disp(1);
  89.     return;
  90. }
  91.  
  92.  
  93. #if 0
  94. int        main()
  95. {
  96.     int        i,ret;
  97.     char    pat[20/2];    /* 最適化後のパターン */
  98.     short    pal[16];    /* パレット */
  99.     
  100.     
  101.     debug(coldat,20);
  102.     puts("");
  103.     
  104.     ret=SOP_selPal(pal,coldat,20);
  105.     if (ret!=0)
  106.         return(-1);
  107.     debug(pal,16);
  108.     puts("");
  109.     
  110.     ret=SOP_optimize(pat,pal,coldat,20);
  111.     for (i=0;i<10;i++)
  112.         printf("%d:%d|",pat[i]/16,pat[i]%16);
  113.     puts("");
  114.     for (i=0;i<10;i++)
  115.         printf("%d:%d\t",pal[pat[i]/16],pal[pat[i]%16]);
  116.     
  117.     
  118.     puts("");
  119.     
  120.     
  121.     return(0);
  122. }
  123. #endif
  124.  
  125.  
  126. /* 色数カウント＆最適16色パレットデータ格納関数 */
  127. int        SOP_selPal(short *pal,short col[],int dotnum,int level)
  128. {
  129.     int        colnum=0;
  130.     int        i,j,ref,min,d,min_i,min_j;
  131.     int        colp,flag;
  132.     short    *buf,*buf2,*buf3;
  133.     
  134.     SPM_MC_tokei();
  135.     
  136.     /* バッファを確保 */
  137.     if ( (buf=malloc(dotnum*2))==NULL)
  138.     {    SPM_MC_ya();    return(-1);    }
  139.     
  140.     /* バッファにコピー */
  141.     _move(col,buf,dotnum*2);
  142.     
  143.     /* 色番号順にソート */
  144.     SOP_qsort(buf,0,dotnum-1);
  145.     
  146.     /* ソート直後のデータを *buf2 に保存 */
  147.     if ( (buf2=malloc(dotnum*2))==NULL)
  148.     {    SPM_MC_ya();    return(-1);    }
  149.     _move(buf,buf2,dotnum*2);
  150.     
  151.     /* バッファ内の整理と色数のカウント...buf[dotnum]に格納 */
  152.     ref=buf[0]; colnum++;
  153.     for (i=1;i<dotnum;i++)
  154.     {
  155.         if (ref!=buf[i])
  156.         { ref=buf[i];buf[colnum]=ref; colnum++; }
  157.     }
  158.     
  159.     /* 16色以内だったら？ */
  160.     if (colnum<=16)
  161.     {
  162.         for (i=0;i<colnum;i++)
  163.             pal[i]=buf[i];
  164.         for (i=colnum;i<16;i++)
  165.             pal[i]=0;
  166.         free(buf);    free(buf2);
  167.         SPM_MC_ya();
  168.         return(0);
  169.     }
  170.     
  171.     
  172.     /* それぞれの色が何度使われているか？...buf3[colnum]に格納 */
  173.     if ( (buf3=(short *)malloc(2*colnum))==NULL)
  174.     {    SPM_MC_ya();    return(-1);    }
  175.     
  176.     _fill_char(buf3,colnum*2,0);
  177.     ref=0;
  178.     for (i=0;i<colnum;i++)
  179.     {
  180.         label:;
  181.         if (buf[i]==buf2[ref])
  182.         {
  183.             ref++; buf3[i]++;
  184.             goto label;
  185.         }
  186.     }
  187.     free(buf2);
  188.     
  189.     
  190.     /* 使われる回数の少ない順にソート(buf3と全く同じようにbufもソート) */
  191.     SOP_qsort2(buf3,buf,0,colnum-1);
  192.     
  193.     free(buf3);        /* buf3も用済み */
  194.     
  195.     /* 末尾の１６色だけ抽出(色コードにして格納) */
  196.     for (i=0;i<16;i++)
  197.         pal[i]=buf[colnum-i-1];
  198.     
  199.     /* 選んだパレットの内、似通った色があるなら一色にまとめる */
  200.     colp=16;flag=0;
  201.     while (1)
  202.     {
  203.         min=1000000000;        /* エレガントさが無い(^^;) */
  204.         for (i=1;i<16;i++)
  205.         {
  206.             for (j=0;j<i;j++)
  207.             {
  208.                 if ( (d=_DIST(pal[i],pal[j])) < min )
  209.                 {
  210.                     min=d;    min_i=i;  min_j=j;
  211.                 }
  212.             }
  213.         }
  214.         
  215.         if (min>level)
  216.             break;
  217.         
  218.         pal[min_i]=buf[colnum-colp-1];
  219.         colp++;
  220.         if (colp>=colnum)
  221.             break;
  222.     }
  223.     
  224.     /* パレットのソート */
  225.     SOP_qsort(pal,0,15);
  226.     
  227.     free(buf);
  228.     
  229.     /* は～い、おつかれ～♪ */
  230.     SPM_MC_ya();
  231.     return(0);
  232. }
  233.  
  234.  
  235.  
  236.  
  237. int        SOP_optimize(char *pat,short palbuf[16],short *buf,int dotnum)
  238. {
  239.     US char    *buf8;    /* ８ビットで格納された最適化済４ビットデータ */
  240.     int        i,j,min,dat,minpal,bytes;
  241.     int        dist,r,g,b;    
  242.     RGB        pal[16];
  243.     
  244.     SPM_MC_fude();
  245.     
  246.     /* パレットデータを計算しやすい形式に直す */
  247.     for (i=0;i<16;i++)
  248.     {
  249.         dat=palbuf[i];
  250.         pal[i].r=_R(dat);
  251.         pal[i].g=_G(dat);
  252.         pal[i].b=_B(dat);
  253.     }
  254.     
  255.     /* バッファの確保 */
  256.     if ( (buf8=(US char *)malloc(dotnum))==NULL)
  257.     {    SPM_MC_ya();    return(-1);    }
  258.     
  259.     /* 差の最も少ない組み合わせを選ぶ */
  260.     for (i=0;i<dotnum;i++)
  261.     {
  262.         min=1000000000;        /* すぐに更新されそうな数 */
  263.         dat = buf[i];
  264.         r = _R(dat);
  265.         g = _G(dat);
  266.         b = _B(dat);
  267.         for (j=0;j<16;j++)
  268.         {
  269.             dist=_DISTC(pal[j].r,pal[j].g,pal[j].b,r,g,b);
  270.             if (min>dist)
  271.             {
  272.                 min=dist;
  273.                 minpal=j;
  274.             }
  275.         }
  276.         buf8[i]=minpal;
  277.     }
  278.     
  279.     /* ８ビットデータを４ビットデータに */
  280.     bytes=((1+dotnum)>>1);
  281.     
  282.     /* 上位４、下位４の順に評価される？ */
  283.     for (i=0;i<bytes;i++)
  284.         pat[i]=(buf8[i*2] << 4)+buf8[i*2+1];
  285.     
  286.     free(buf8);
  287.     SPM_MC_ya();
  288.     return(0);
  289. }
  290.  
  291.  
  292.  
  293. /* クイックソート関数 */
  294.  
  295. void    SOP_qsort(short a[],int left,int right)
  296. {
  297.     int        s,t,i,j;
  298.     
  299.     if (left<right)
  300.     {
  301.         s=a[(left+right)/2];
  302.         i=left-1; j=right+1;
  303.         while(1)
  304.         {
  305.             while (a[++i]<s)    ;
  306.             while (a[--j]>s)    ;
  307.             if (i>=j)
  308.                 break;
  309.             t=a[i]; a[i]=a[j]; a[j]=t;
  310.         }
  311.         
  312.         SOP_qsort(a,left,i-1);
  313.         SOP_qsort(a,j+1,right);
  314.     }
  315.     return;
  316. }
  317.  
  318.  
  319. /* クイックソート２ */
  320. static    void    SOP_qsort2(short a[],short b[],int left,int right)
  321. {
  322.     int        s,t,i,j;
  323.     
  324.     if (left<right)
  325.     {
  326.         s=a[(left+right)/2];
  327.         i=left-1; j=right+1;
  328.         while(1)
  329.         {
  330.             while (a[++i]<s)    ;
  331.             while (a[--j]>s)    ;
  332.             if (i>=j)
  333.                 break;
  334.             t=a[i]; a[i]=a[j]; a[j]=t; t=b[i]; b[i]=b[j]; b[j]=t;
  335.         }
  336.         
  337.         SOP_qsort(a,left,i-1);
  338.         SOP_qsort(a,j+1,right);
  339.     }
  340.     return;
  341. }
  342.  
  343.  
  344.  
  345.  
  346.  
  347.  
  348.