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
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];
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
00244 countbuff[i] = (countbuff[i] + countbuff[i - 1]);
00245 }
00246 for (i = num - 1; i >= 0; i--) {
00247
00248 temp = buff[i];
00249 table2dwork[--countbuff[ temp ]] = buff[i];
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
00281 countbuff[i] = (countbuff[i] + countbuff[i - 1]);
00282 }
00283 for (i = num - 1; i >= 0; i--) {
00284
00285
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
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
00359 size_t temp = INT_MAX;
00360
00361 #ifdef DEBUG_BSE
00362 size_t ii = 0;
00363 #endif
00364
00365
00366 if( rotasize & 0x01){
00367 rotasize--;
00368 }
00369 if(buffsize > temp + 1){
00370
00371 return edk_ArgumentException;
00372 }
00373 if(rotasize < buffsize * 2){
00374 return edk_ArgumentException;
00375 }
00376 if(buffworksize < buffsize){
00377 return edk_ArgumentException;
00378 }
00379 if(destsize < 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){
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
00428 }
00429 DBSE_PRINTF("\n");
00430 # endif
00431
00432 }
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
00509 memcpy(rotabuff,buff,buffsize);
00510 memcpy(rotabuff + buffsize,buff,buffsize);
00511
00512
00513
00514
00515
00516
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
00529 if(rotabuff){
00530 free(rotabuff);
00531 }
00532 if(pp){
00533 free(pp);
00534
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 }