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

dkcBlockSort.c

#include "dkcBlockSort.h"

dkcBlockSort.cのインクルード依存関係図

ソースコードを見る。

マクロ定義

#define DKUTIL_C_BLOCKSORT_C
#define DEBUG_BSE
#define DBSE_PRINTF   printf
#define dkcfBSE_BASIC   bse_basic_logic
#define dkcfBSE_NORMAL   bse_logic01
#define dkcfBSE_FAST   bse_logic01
#define dkcfBSD_BASIC   bsd_basic_logic

型定義

typedef BYTE ** pa_type

関数

static int bs_insertion_sort_to_table (BYTE *rotabuff, size_t cycle, size_t len, BYTE **tablework)
static void free_table2d (BYTE **table2d, size_t table_height_num)
static BYTE ** alloc_table2d (size_t width, size_t height)
static int bse_sorted_table_to_data (BYTE *buff, size_t buffsize, BYTE *rotabuff, BYTE **table2d, size_t twidth, DKC_BLOCKSORT_INFO *pinfo)
static int bse_basic_logic (void *buff, size_t buffsize, DKC_BLOCKSORT_INFO *pinfo)
static int bsd_basic_logic (void *buff, size_t buffsize, DKC_BLOCKSORT_INFO *pinfo)
int WINAPI dkcBlockSortEncode (void *buff, size_t buffsize, DKC_BLOCKSORT_INFO *p)
int WINAPI dkcBlockSortDecode (void *buff, size_t buffsize, DKC_BLOCKSORT_INFO *p)


説明

作者:
d金魚
から:
2004/10/17
覚え書き:
ソースコード構築の再に使用したメモ http://d.hatena.ne.jp/studiokingyo/20041011

仕様 -BSEとは block sort encodeの略である 巷での牛問題とは関係ない。 -BSDとは block sort decodeの略である いわいるOSの類とは関係ない 。

licence

BSD Licence

うんちく1

rotabuffをbuffの二倍のサイズで用意する事により、
buffsize * buffsize byte 必要なシフトバッファを減らしている。
例: 
abcは abc bca cab のパターンがある。3*3 == 9である。しかし、
char *p = abcabc; で p[0] だとabc  p[1] だと=[2] だと cab p[3] でabc...

謝辞

これらのBlockSortのソースは
M.Hiroi's Home Page
http://www.geocities.co.jp/SiliconValley-Oakland/1680/
を参考にして作りました。
この場をお借りして感謝申し上げます。m(_)m

dkcBlockSort.c で定義されています。


マクロ定義

#define DBSE_PRINTF   printf
 

dkcBlockSort.c41 行で定義されています。

#define DEBUG_BSE
 

dkcBlockSort.c39 行で定義されています。

#define dkcfBSD_BASIC   bsd_basic_logic
 

dkcBlockSort.c596 行で定義されています。

参照元 dkcBlockSortDecode().

#define dkcfBSE_BASIC   bse_basic_logic
 

dkcBlockSort.c589 行で定義されています。

参照元 dkcBlockSortEncode().

#define dkcfBSE_FAST   bse_logic01
 

dkcBlockSort.c594 行で定義されています。

#define dkcfBSE_NORMAL   bse_logic01
 

dkcBlockSort.c591 行で定義されています。

#define DKUTIL_C_BLOCKSORT_C
 

dkcBlockSort.c35 行で定義されています。


型定義

typedef BYTE** pa_type
 

dkcBlockSort.c485 行で定義されています。


関数

static BYTE** alloc_table2d size_t  width,
size_t  height
[static]
 

引数:
width[in] 横のサイズ
height[in] 縦のサイズ
覚え書き:
tableのイメージ
   0          1       2     3 width
 0 p[0][0] p[0][1] p[0][2] ..
 1 ...
 2 ...
 3 ...     p[3][1] ...
height

dkcBlockSort.c96 行で定義されています。

参照先 BYTE, free_table2d(), と NULL.

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 }

static int bs_insertion_sort_to_table BYTE rotabuff,
size_t  cycle,
size_t  len,
BYTE **  tablework
[static]
 

dkcBlockSort.c44 行で定義されています。

参照先 BYTE.

参照元 bsd_basic_logic(), と bse_basic_logic().

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 }

static int bsd_basic_logic void *  buff,
size_t  buffsize,
DKC_BLOCKSORT_INFO pinfo
[static]
 

dkcBlockSort.c540 行で定義されています。

参照先 bs_insertion_sort_to_table(), BYTE, dkc_BlockSortInfo::mOffset, と NULL.

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 }

static int bse_basic_logic void *  buff,
size_t  buffsize,
DKC_BLOCKSORT_INFO pinfo
[static]
 

dkcBlockSort.c490 行で定義されています。

参照先 bs_insertion_sort_to_table(), bse_sorted_table_to_data(), BYTE, と NULL.

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 }

static int bse_sorted_table_to_data BYTE buff,
size_t  buffsize,
BYTE rotabuff,
BYTE **  table2d,
size_t  twidth,
DKC_BLOCKSORT_INFO pinfo
[static]
 

dkcBlockSort.c457 行で定義されています。

参照先 BYTE, FALSE, dkc_BlockSortInfo::mOffset, dkc_BlockSortInfo::mResultPointer, と TRUE.

参照元 bse_basic_logic().

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 }

int WINAPI dkcBlockSortDecode void *  buff,
size_t  buffsize,
DKC_BLOCKSORT_INFO p
 

dkcBlockSort.c604 行で定義されています。

参照先 dkcfBSD_BASIC.

00604                                                                                {
00605     return dkcfBSD_BASIC(buff,buffsize,p);
00606 }

int WINAPI dkcBlockSortEncode void *  buff,
size_t  buffsize,
DKC_BLOCKSORT_INFO p
 

引数:
buff[in][out] ソートするデータ
buffsize[in] buffの有効範囲のバイト単位のサイズ
p[out] 処理結果を返す。この関数の戻り値が成功を示さなければ正しい処理結果を返さない。
戻り値:
edk_SUCCEEDEDで成功。それ以外は処理を完了されていない。
覚え書き:
buffに入れたデータはメチャクチャになっているので buffにいったんぶち込んだデータをこの関数が失敗した再、再利用してはいけない。

dkcBlockSort.c599 行で定義されています。

参照先 dkcfBSE_BASIC.

00600 {
00601     return dkcfBSE_BASIC(buff,buffsize,p);
00602 }

static void free_table2d BYTE **  table2d,
size_t  table_height_num
[static]
 

dkcBlockSort.c68 行で定義されています。

参照先 NULL.

参照元 alloc_table2d().

00068                                                                 {
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 }


dkutil_cに対してSat Sep 10 09:24:05 2005に生成されました。  doxygen 1.4.4