メインページ | アルファベット順一覧 | 構成 | ファイル一覧 | 構成メンバ | ファイルメンバ | 関連ページ

# dkcBlockSort.c

説明を見る。

    00001
    00035 #define DKUTIL_C_BLOCKSORT_C
    00036 #include "dkcBlockSort.h"
    00037
    00038
    00039 #define DEBUG_BSE
    00040
    00041 #define DBSE_PRINTF printf
    00042
    00043
    00044 static int bs_insertion_sort_to_table(BYTE *rotabuff,
    00045                                                                             size_t cycle,size_t len,
    00046                                                                             BYTE **tablework)
    00047 {
    00048     size_t i,j;
    00049
    00050     BYTE *t;
    00051     for( i = 0; i < cycle;i++ ){
    00052         tablework[i] = (BYTE *)&rotabuff[i];
    00053     }
    00054     for( i = 1;i < cycle;i++)
    00055     {
    00056         t = tablework[i];
    00057         for( j = i - 1;j >= 0 && j != UINT_MAX && memcmp( t,tablework[j],len) < 0;j--)
    00058         {
    00059
    00060             tablework[j + 1] = tablework[j];
    00061
    00062         }
    00063         tablework[j + 1] = t;
    00064     }
    00065     return edk_SUCCEEDED;
    00066 }
    00067
    00068 static void free_table2d(BYTE **table2d,size_t table_height_num){
    00069     size_t i;
    00070
    00071     if(table2d){
    00072         for(i = 0;i<table_height_num;i++){
    00073             if(NULL != table2d[i]){
    00074                 free(table2d[i]);
    00075             }
    00076         }
    00077         free((void *)table2d);
    00078     }
    00079
    00080 }
    00081
    00096 static BYTE **alloc_table2d(size_t width,size_t height)
    00097 {
    00098     size_t i,t;
    00099     BYTE **table2d = (BYTE **)malloc(height);
    00100
    00101     if(NULL==table2d){
    00102         goto Error;
    00103     }
    00104     memset(table2d,(int)NULL,height);
    00105
    00106     t = height / sizeof(BYTE *);
    00107
    00108     for(i=0;i<t;i++){
    00109         table2d[i] = (BYTE *)malloc(width);
    00110         if(NULL==table2d[i]){
    00111             goto Error;
    00112         }
    00113     }
    00114
    00115     return table2d;
    00116 Error:
    00117     free_table2d(table2d,width);
    00118     return NULL;
    00119 }
    00120
    00121
    00122 #if 0
    00123
    00128 static int WINAPI bse_dc_sort_lead2byte(size_t num, const BYTE *a, BYTE **b)
    00129 {
    00130     int i, x;
    00131     size_t ii,temp;
    00132     BYTE *begin_offset = &a[0];
    00133
    00134
    00135
    00136     for (ii = 0; ii < num; ii++){
    00137         temp = (a[i] << 8)
    00138         count[   ]++;
    00139     }
    00140
    00141     for (i = 1; i <= Max_ - Min_; i++){
    00142         //count[i] += count[i - 1];
    00143         count[i] = (char)(count[i] + count[i - 1]);
    00144     }
    00145     for (i = num - 1; i >= 0; i--) {
    00146         x = a[i] - Min_; b[--count[x]] = a[i]; //debugged
    00147     }
    00148     dkcFree((void **)&count);
    00149     return edk_SUCCEEDED;
    00150
    00151
    00152 }
    00153
    00154 static int bse_logic01_helper(void *dest,size_t dsize){
    00155     BYTE *buff = NULL,rotabuff = NULL;
    00156     size_t buffsize = dsize,rotasize= dsize * 2;
    00157     BYTE **table2d = NULL;
    00158     size_t table_width = dsize,table_height = dsize;
    00159
    00160     BYTE table_init_flag = FALSE;
    00161
    00162     int r = edk_OutOfMemory;
    00163
    00164     buff = malloc(buffsize);
    00165     if(NULL==buff){
    00166         return r;
    00167     }
    00168
    00169     rotabuff = malloc(rotasize);
    00170     if(NULL==rotabuff){
    00171         goto END;
    00172     }
    00173
    00174     table2d = malloc(table_height);
    00175     if(NULL==table2d){
    00176         goto END;
    00177     }
    00178     memset(table2d,(int)NULL,table_height);
    00179
    00180     table_init_flag = TRUE;
    00181
    00182     for(i=0;i<table_height;i++){
    00183         table2d[i] = malloc(table_width);
    00184         if(NULL==table2d[i]){
    00185             goto END;
    00186         }
    00187     }
    00188
    00189
    00190
    00191
    00192     r = bse_logic01(
    00193         dest,dsize,
    00194         buff,buffsize,
    00195         rotabuff,rotasize,
    00196         sortwork,sortworksize,
    00197         table2d,table_width,table_height
    00198     );
    00199 END:
    00200     if(table2d){
    00201         if(table_init_flag){
    00202             for(i = 0;i<table_height;i++){
    00203                 if(NULL != table2d[i]){
    00204                     free(table2d[i]);
    00205                 }
    00206             }
    00207         }
    00208         free((void *)table2d);
    00209     }
    00210     if(rotabuff){free(rotabuff);}
    00211     if(buff){free(buff);}
    00212
    00213
    00214
    00215
    00216
    00217     return r;
    00218 }
    00219
    00220
    00221
    00222
    00223
    00224
    00226 static int bse_distcount1_to_table( size_t *countbuff,size_t countsize,
    00227                                                                         BYTE **table2dwork,size_t table_width_size)
    00228 {
    00229     size_t temp,i;
    00230     size_t num = table_width_size;
    00231     dkcmASSERT("だめだめ");
    00232     //出現頻度を測定
    00233     for(i = 0;i<num;i++){
    00234 #   ifdef DEBUG
    00235         temp = buff[i];
    00236         countbuff[temp]++;
    00237 #   else
    00238         countbuff[ buff[ i ] ]++;
    00239 #   endif
    00240     }
    00241
    00242   for (i = 1; i <= num; i++){
    00243         //count[i] += count[i - 1];
    00244         countbuff[i] = (countbuff[i] + countbuff[i - 1]);
    00245     }
    00246     for (i = num - 1; i >= 0; i--) {
    00247         //x = a[i] - Min_;
    00248         temp = buff[i];
    00249         table2dwork[--countbuff[ temp ]] = buff[i]; //debugged
    00250     }
    00251 }
    00252
    00253 static int bse_distcount2_to_table(size_t *countbuff,size_t countsize,
    00254                                                                         BYTE **table2dwork,size_t table_width_size,
    00255                                                                         BYTE **get_result)
    00256 {
    00257     size_t i;
    00258     size_t temp;
    00259
    00260     if(table_widht_size == 1){
    00261         return bse_distcount1_to_table(countbuff,countsize,table2dwork,table_width_size);
    00262     }else if(table_width_size == 0){//アホは削除
    00263         return edk_FAILED;
    00264     }
    00265
    00266
    00267 #   define BSE_GET_VALUE(i) ((table2dwork[(i)] << 8) + table2dwork[(i) + 1])
    00268
    00269     //出現頻度を測定
    00270     for(i = 0;i<buffsize;i++){
    00271 #   ifdef DEBUG
    00272         temp = (table2dwork[i] << 8) + table2dwork[i + 1];
    00273         countbuff[temp]++;
    00274 #   else
    00275         countbuff[ BSE_GET_VALUE(i) ]++;
    00276 #   endif
    00277     }
    00278
    00279   for (i = 1; i <= buffsize; i++){
    00280         //count[i] += count[i - 1];
    00281         countbuff[i] = (countbuff[i] + countbuff[i - 1]);
    00282     }
    00283     for (i = num - 1; i >= 0; i--) {
    00284         //x = a[i] - Min_;
    00285         //b[--count[ x ]] = a[i]; //debugged
    00286         temp = BSE_GET_VALUE(i);
    00287         get_result[--countbuff[ x ] ] = table2dwork[i]
    00288     }
    00289
    00290     return edk_SUCCEEDED;
    00291
    00292 #   undef BSE_GET_VALUE
    00293 }
    00294
    00295
    00296 static int  bse_ternary_qsort_after_distcuont2_to_table
    00297
    00305
    00306
    00307 static int bse_distcount2_ternary_qsort_to_table(
    00308                                                                         size_t *countbuff,size_t countsize,
    00309                                                                         BYTE **table2dwork,size_t table_width_size,
    00310                                                                         BYTE **get_result)
    00311 {
    00312     size_t i;
    00313     size_t temp;
    00314     int r;
    00315
    00316
    00317     switch(table_width_size){
    00318     case 0://アホは削除
    00319         return edk_FAILED;
    00320     case 1:
    00321         return bse_distcount1_to_table(countbuff,countsize,table2dwork,table_width_size);
    00322     case 2:
    00323         return bse_distcount2_to_table(countbuff,coubtsize,table2dwork,table_width_size);
    00324     default:
    00325         break;
    00326     }
    00327
    00328     r = bse_distcount2_to_table(countbuff,coubtsize,table2dwork,table_width_size)
    00329
    00330     if(DKUTIL_FAILED(r)){
    00331         return r;
    00332     }
    00333
    00334     //bse_ternary_qsort_after_distcuont2_to_table
    00335
    00336     return r;
    00337 }
    00338
    00350 static int bse_logic01(BYTE *dest,size_t destsize,
    00351                                                 BYTE *buff,size_t buffsize,
    00352                                             BYTE *rotabuff,size_t rotasize,
    00353                                             size_t *countbuff,size_t countsize,
    00354                                             BYTE **table2dwork,size_t table_width_size,size_t table_height_size)
    00355 {
    00356
    00357     size_t i;
    00358     //BYTE *tb = NULL;
    00359     size_t temp = INT_MAX;
    00360
    00361 #ifdef DEBUG_BSE
    00362     size_t ii = 0;
    00363 #endif
    00364
    00365     //エラー条件をフィルタリング
    00366     if(/*rotasize % 2 != 0*/ rotasize & 0x01){
    00367         rotasize--;
    00368     }
    00369     if(buffsize > temp + 1){
    00370         //このサイズだとオーバーフロー。のはず･･･。
    00371         return edk_ArgumentException;
    00372     }
    00373     if(rotasize < buffsize * 2){//rotasizeが小さい
    00374         return edk_ArgumentException;
    00375     }
    00376     if(buffworksize < buffsize){//buffworksize
    00377         return edk_ArgumentException;
    00378     }
    00379     if(destsize < buffsize){//buffsizeより小さかったらモグリ
    00380         return edk_ArgumentException;
    00381     }
    00382     if(table_width_size != table_height_size){//テーブルのサイズが違うようで･･･
    00383         return edk_ArgumentException;
    00384     }
    00385     for(i=0;i<table_height_size;i++){
    00386         if(table2dwork[i] == NULL){//くそ！変な配列入れあがって
    00387             return edk_ArgumentException;
    00388         }
    00389     }
    00390     if(countsize < 256 * 256){//256 * 256 USHRT_MAX ?? byte 必要
    00391         return edk_ArgumentException;
    00392     }
    00393
    00394     //初期化 (うんちく１を参照）
    00395
    00396     memcpy(rotabuff,buff,buffsize);
    00397     memcpy(rotabuff + buffsize,buff,buffsize);
    00398
    00399
    00400
    00401 #ifdef DEBUG_BSE
    00402     DBSE_PRINTF("rotabuff:\t");
    00403     for(i = 0;i<rotasize;i++){
    00404         DBSE_PRINTF("%c",rotabuff[i]);
    00405     }
    00406     DBSE_PRINTF("\n");
    00407 #endif
    00408     temp = buffsize;
    00409     for(i = 0;i<temp;i++)
    00410     {
    00411         memcpy(buffwork,rotabuff + i,buffsize);
    00412
    00413 #   ifdef DEBUG_BSE
    00414         DBSE_PRINTF("%d:\t",i);
    00415         for(ii = 0;ii<buffsize;ii++){
    00416             DBSE_PRINTF("%c",(char)buffwork[ii]);
    00417         }
    00418         DBSE_PRINTF("\t");
    00419 #   endif
    00420
    00421
    00422 #   ifdef DEBUG_BSE
    00423         dkcRotateShiftRightMemory(dest,buffsize,i);
    00424         for(ii = 0;ii<buffsize;ii++){
    00425
    00426             DBSE_PRINTF("%c",*(dest + i + buffsize - 1));
    00427             //DBSE_PRINTF("%c",(char)dest[ii]);
    00428         }
    00429         DBSE_PRINTF("\n");
    00430 #   endif
    00431
    00432     }//end of for
    00433     return edk_SUCCEEDED;
    00434
    00435 }
    00436
    00437
    00438
    00439 static int bse_target_to_table(void *buff,size_t buffsize,
    00440                                                              BYTE **table2d,size_t twidth,size_t theight)
    00441 {
    00442     size_t i;
    00443     if(buffsize > twidth){
    00444         return edk_ArgumentException;
    00445     }
    00446
    00447     for(i = 0;i<theight;i++)
    00448     {
    00449         memcpy(table2d[i],buff,buffsize);
    00450         dkcRotateShiftRightMemory(buff,buffsize,1);
    00451     }
    00452     return edk_SUCCEEDED;
    00453 }
    00454
    00455 #endif
    00456
    00457 static int bse_sorted_table_to_data(BYTE *buff,size_t buffsize,BYTE *rotabuff,
    00458                                                                         BYTE **table2d,size_t twidth,DKC_BLOCKSORT_INFO *pinfo)
    00459 {
    00460     size_t i;
    00461     BYTE *pout = (BYTE *)buff;
    00462     BYTE *pt;
    00463     BOOL flag = FALSE;
    00464
    00465     if(buffsize < twidth){
    00466         return edk_ArgumentException;
    00467     }
    00468
    00469     for(i = 0;i<twidth;i++){
    00470         pt = table2d[i];
    00471         if(rotabuff == pt){
    00472             pinfo->mOffset = i;
    00473             flag = TRUE;
    00474         }
    00475         pout[i] = pt[twidth - 1];
    00476     }
    00477     pinfo->mResultPointer = buff;
    00478
    00479     if(flag){
    00480         return edk_SUCCEEDED;
    00481     }else{
    00482         return edk_FAILED;
    00483     }
    00484 }
    00485 typedef BYTE **pa_type;
    00486
    00487
    00488
    00489
    00490 static int bse_basic_logic(void *buff,size_t buffsize,DKC_BLOCKSORT_INFO *pinfo)
    00491 {
    00492     int r = edk_OutOfMemory;
    00493     BYTE *rotabuff = NULL;
    00494     size_t rotasize = buffsize * 2;
    00495
    00496
    00497     BYTE **pp = (BYTE **)malloc(buffsize * sizeof(BYTE *));
    00498     if(NULL==pp){
    00499         goto END;
    00500     }
    00501
    00502     rotabuff = (BYTE *)malloc(rotasize);
    00503     if(!rotabuff){
    00504         goto END;
    00505     }
    00506
    00507
    00508     //テーブルにBlock sortに使うシフトされたデータをセットする
    00509     memcpy(rotabuff,buff,buffsize);
    00510     memcpy(rotabuff + buffsize,buff,buffsize);
    00511
    00512
    00513     /*r = bse_target_to_table(buff,buffsize,pp,ppsize,1);
    00514
    00515     if(DKUTIL_FAILED(r)){
    00516         goto END;
    00517     }*/
    00518     //テーブルを元に辞書順ソートする。
    00519     r = bs_insertion_sort_to_table(rotabuff,buffsize,buffsize,pp);
    00520
    00521     if(DKUTIL_FAILED(r)){
    00522         goto END;
    00523     }
    00524     //辞書順にソートされたテーブルから出力データを求める。
    00525     r = bse_sorted_table_to_data((BYTE *)buff,buffsize,(BYTE *)rotabuff,pp,buffsize,pinfo);
    00526
    00527 END:
    00528     //free_table2d(pp,buffsize);
    00529     if(rotabuff){
    00530         free(rotabuff);
    00531     }
    00532     if(pp){
    00533         free(pp);
    00534         //free_table2d(pp,1);
    00535     }
    00536     return r;
    00537 }
    00538
    00539
    00540 static int bsd_basic_logic(void *buff,size_t buffsize,DKC_BLOCKSORT_INFO *pinfo)
    00541 {
    00542     size_t i,offset;
    00543     BYTE *p,*pout;
    00544     size_t ppsize = sizeof(BYTE *) * buffsize;
    00545     BYTE **pp = NULL;
    00546     int r = edk_OutOfMemory;
    00547     BYTE *pwork = (BYTE *)malloc(buffsize);
    00548
    00549     if(NULL==pwork){
    00550         goto END;
    00551     }
    00552     memcpy(pwork,buff,buffsize);
    00553
    00554
    00555     pp = (BYTE **)malloc(ppsize);
    00556     if(NULL==pp){
    00557         goto END;
    00558     }
    00559
    00560     //テーブルを元に辞書順ソートする。
    00561     r = bs_insertion_sort_to_table((BYTE *)pwork,buffsize,1,pp);
    00562     if(DKUTIL_FAILED(r)){
    00563         goto END;
    00564     }
    00565
    00566     offset = pinfo->mOffset;
    00567     p = pp[offset];
    00568     pout = (BYTE *)buff;
    00569     for(i = 0;i<buffsize;i++)
    00570     {
    00571         pout[i] = *p;
    00572         //二次使用
    00573         offset = p - (BYTE *)pwork;
    00574         p = pp[offset];
    00575     }
    00576
    00577 END:
    00578     if(pp){
    00579         free(pp);
    00580     }
    00581     if(pwork){
    00582         free(pwork);
    00583     }
    00584
    00585     return r;
    00586
    00587 }
    00588
    00589 #define dkcfBSE_BASIC bse_basic_logic
    00590
    00591 #define dkcfBSE_NORMAL bse_logic01
    00592
    00593
    00594 #define dkcfBSE_FAST bse_logic01
    00595
    00596 #define dkcfBSD_BASIC bsd_basic_logic
    00597
    00598
    00599 int WINAPI dkcBlockSortEncode(void *buff,size_t buffsize,DKC_BLOCKSORT_INFO *p)
    00600 {
    00601     return dkcfBSE_BASIC(buff,buffsize,p);
    00602 }
    00603
    00604 int WINAPI dkcBlockSortDecode(void *buff,size_t buffsize,DKC_BLOCKSORT_INFO *p){
    00605     return dkcfBSD_BASIC(buff,buffsize,p);
    00606 }