// ハフマン解凍ソフト // include ---------- #include #include #include // define ----------- // 各型とバイト数の関係( 環境によって変わりますが・・・ ) // int : ４バイト(0〜4,294,967,295) // short : ２バイト(0〜65,535) // char : １バイト(0〜255) // data type -------- // 数値ごとの出現数や算出されたエンコード後のビット列や、結合部分の情報等の構造体 struct HUFFMAN_NODE { int Weight ; // 出現数( 結合データでは出現数を足したモノ ) int BitNum ; // 圧縮後のビット列のビット数( 結合データでは使わない ) unsigned char BitArray[32] ; // 圧縮後のビット列( 結合データでは使わない ) int Index ; // 結合データに割り当てられた参照インデックス( 0 or 1 ) int ParentNode ; // このデータを従えている結合データの要素配列のインデックス int ChildNode[2] ; // このデータが結合させた２要素の要素配列インデックス( 結合データではない場合はどちらも -1 ) } ; // 圧縮データの情報 struct HUFFMAN_ENCODE_INFO { int OriginalSize ; // 圧縮前のデータのサイズ(バイト数) int PressSize ; // 圧縮後のデータのサイズ(この構造体のサイズも含む) int Weight[256] ; // 各数値ごとの出現回数 } ; // proto type ------- // 圧縮データを解凍 // // 戻り値:解凍後のサイズ -1 はエラー Dest に NULL を入れると解凍データ格納に必要なサイズが返る int Huffman_Decode( void *Press, void *Dest ) ; // code ------------- // メイン関数 // argc:引数の数( 最初の1個は exe ファイルのパスなので０個になることはない ) // argv:引数の文字列配列へのポインタ( 最初の文字列は exe ファイルのパス文字列 ) int main( int argc, char **argv ) { void *buf, *dest_buf ; int size, dest_size ; // ソフトのタイトルを出力 printf( "Huffman Decode Soft\n\n" ) ; // ファイル名の指定がなかったらヘルプを表示 if( argc != 2 ) { printf( " HuffmanDecode.exe FilePath\n" ) ; return 0 ; } // ファイルを丸ごと読み込む { FILE *fp ; // ファイルを開く fp = fopen( argv[1], "rb" ) ; if( fp == NULL ) { printf( " File open Error!!\n" ) ; return 0 ; } // ファイルサイズを調べる { // ファイルポインタをファイルの末尾に fseek( fp, 0L, SEEK_END ) ; // ファイルの末尾で現在のファイルポインタアドレスを取得すればそれはファイルのサイズ size = ftell( fp ) ; // ファイルポインタをファイルの先頭に戻す fseek( fp, 0L, SEEK_SET ) ; } // ファイルを丸ごと読み込む為のメモリを確保する buf = malloc( size ) ; if( buf == NULL ) { printf( " Memory alloc Error!!\n" ) ; return 0 ; } // ファイルを丸ごと読み込む fread( buf, size, 1, fp ) ; // ファイルを閉じる fclose( fp ) ; } // 圧縮したデータを解凍する { // 解凍した時のデータのサイズを取得する dest_size = Huffman_Decode( buf, NULL ) ; // 解凍したデータを格納するためのメモリを確保する dest_buf = malloc( dest_size ) ; if( dest_buf == NULL ) { printf( " Memory alloc Error!!\n" ) ; return 0 ; } // 解凍したデータを確保したメモリ領域に保存する Huffman_Decode( buf, dest_buf ) ; // 圧縮データは解放する free( buf ) ; } // 解凍したデータをファイルに保存する { FILE *fp ; char FileName[256] ; // 拡張子を『dec』に変更して保存する { char *LastPeriod ; // 元のファイルのファイルパスをコピーする strcpy( FileName, argv[1] ) ; // 最後の『.』のアドレスを取得する LastPeriod = strrchr( FileName, '.' ) ; // ピリオドがなかった場合は拡張子が無いと判断して『.dec』を末尾に追加する if( LastPeriod == NULL ) { strcat( FileName, ".dec" ) ; } else { // あった場合はピリオドの後の文字列を『dec』にしてしまう strcpy( LastPeriod + 1, "dec" ) ; } } // 解凍データを保存するファイルを開く fp = fopen( FileName, "wb" ) ; // 解凍データを丸ごと書き込み fwrite( dest_buf, dest_size, 1, fp ) ; // ファイルを閉じる fclose( fp ) ; // 解凍データを解放する free( dest_buf ) ; } // 終了 return 0 ; } // 圧縮データを解凍 // // 戻り値:解凍後のサイズ -1 はエラー Dest に NULL を入れると解凍データ格納に必要なサイズが返る int Huffman_Decode( void *Press, void *Dest ) { // 結合データと数値データ、０〜２５５までが数値データ HUFFMAN_NODE Node[256 + 255] ; int PressSizeCounter, DestSizeCounter, DestSize ; unsigned char *PressPoint, *DestPoint ; int i ; HUFFMAN_ENCODE_INFO EncodeInfo ; // void 型のポインタではアドレスの操作が出来ないので unsigned char 型のポインタにする PressPoint = ( unsigned char * )Press ; DestPoint = ( unsigned char * )Dest ; // 圧縮データの情報を取得する memcpy( &EncodeInfo, Press, sizeof( HUFFMAN_ENCODE_INFO ) ) ; // Dest が NULL の場合は 解凍後のデータのサイズを返す if( Dest == NULL ) return EncodeInfo.OriginalSize ; // 解凍後のデータのサイズを取得する DestSize = EncodeInfo.OriginalSize ; // 各数値の結合データを構築する { int NodeIndex, MinNode1, MinNode2 ; int NodeNum, DataNum ; // 数値データを初期化する for( i = 0 ; i < 256 ; i ++ ) { Node[i].Weight = EncodeInfo.Weight[i] ; // 出現数は保存しておいたデータからコピー Node[i].ChildNode[0] = -1 ; // 数値データが終点なので -1 をセットする Node[i].ChildNode[1] = -1 ; // 数値データが終点なので -1 をセットする Node[i].ParentNode = -1 ; // まだどの要素とも結合されていないので -1 をセットする } // 出現数の少ない数値データ or 結合データを繋いで // 新しい結合データを作成、全ての要素を繋いで残り１個になるまで繰り返す // (圧縮時と同じコードです) DataNum = 256 ; // 残り要素数 NodeNum = 256 ; // 次に新しく作る結合データの要素配列のインデックス while( DataNum > 1 ) { // 出現数値の低い要素二つを探す { MinNode1 = -1 ; MinNode2 = -1 ; // 残っている要素全てを調べるまでループ NodeIndex = 0 ; for( i = 0 ; i < DataNum ; NodeIndex ++ ) { // もう既に何処かの要素と結合されている場合は対象外 if( Node[NodeIndex].ParentNode != -1 ) continue ; i ++ ; // まだ有効な要素をセットしていないか、より出現数値の // 少ない要素が見つかったら更新 if( MinNode1 == -1 || Node[MinNode1].Weight > Node[NodeIndex].Weight ) { // 今まで一番出現数値が少なかったと思われた // 要素は二番目に降格 MinNode2 = MinNode1 ; // 新しい一番の要素の要素配列のインデックスを保存 MinNode1 = NodeIndex ; } else { // 一番よりは出現数値が多くても、二番目よりは出現数値が // 少ないかもしれないので一応チェック(又は二番目に出現数値の // 少ない要素がセットされていなかった場合もセット) if( MinNode2 == -1 || Node[MinNode2].Weight > Node[NodeIndex].Weight ) { MinNode2 = NodeIndex ; } } } } // 二つの要素を繋いで新しい要素(結合データ)を作る Node[NodeNum].ParentNode = -1 ; // 新しいデータは当然まだ何処とも繋がっていないので -1 Node[NodeNum].Weight = Node[MinNode1].Weight + Node[MinNode2].Weight ; // 出現数値は二つの数値を足したものをセットする Node[NodeNum].ChildNode[0] = MinNode1 ; // この結合部で 0 を選んだら出現数値が一番少ない要素に繋がる Node[NodeNum].ChildNode[1] = MinNode2 ; // この結合部で 1 を選んだら出現数値が二番目に少ない要素に繋がる // 結合された要素二つに、自分達に何の値が割り当てられたかをセットする Node[MinNode1].Index = 0 ; // 一番出現数値が少ない要素は 0 番 Node[MinNode2].Index = 1 ; // 二番目に出現数値が少ない要素は 1 番 // 結合された要素二つに、自分達を結合した結合データの要素配列インデックスをセットする Node[MinNode1].ParentNode = NodeNum ; Node[MinNode2].ParentNode = NodeNum ; // 要素の数を一個増やす NodeNum ++ ; // 残り要素の数は、一つ要素が新しく追加された代わりに // 二つの要素が結合されて検索の対象から外れたので // 結果 1 - 2 で -1 DataNum -- ; } } // 解凍処理 { unsigned char *PressData ; int PressBitCounter, PressBitData, Index, NodeIndex ; // 圧縮データ本体の先頭アドレスをセット // (圧縮データ本体は元のサイズ、圧縮後のサイズ、各数値の出現数等を // 格納するデータ領域の後にある) PressData = PressPoint + sizeof( HUFFMAN_ENCODE_INFO ) ; // 解凍したデータの格納アドレスを初期化 DestSizeCounter = 0 ; // 圧縮データの参照アドレスを初期化 PressSizeCounter = 0 ; // 圧縮ビットデータのカウンタを初期化 PressBitCounter = 0 ; // 圧縮データの１バイト目をセット PressBitData = PressData[PressSizeCounter] ; // 圧縮前のデータサイズになるまで解凍処理を繰り返す for( DestSizeCounter = 0 ; DestSizeCounter < DestSize ; DestSizeCounter ++ ) { // ビット列から数値データを検索する { // 結合データの天辺は一番最後の結合データが格納される５１０番目(０番から数える) // 天辺から順に下に降りていく NodeIndex = 510 ; // 数値データに辿り着くまで結合データを下りていく while( Node[NodeIndex].ChildNode[0] != -1 || Node[NodeIndex].ChildNode[1] != -1 ) { // もし PressBitData に格納されている全ての // ビットデータを使い切ってしまった場合は次の // ビットデータをセットする if( PressBitCounter == 8 ) { PressSizeCounter ++ ; PressBitData = PressData[PressSizeCounter] ; PressBitCounter = 0 ; } // １ビット取得する Index = PressBitData & 1 ; // 使用した１ビット分だけ右にシフトする PressBitData >>= 1 ; // 使用したビット数を一個増やす PressBitCounter ++ ; // 次の要素(結合データか数値データかはまだ分からない)に移る NodeIndex = Node[NodeIndex].ChildNode[Index] ; } } // 辿り着いた数値データを出力 DestPoint[DestSizeCounter] = (unsigned char)NodeIndex ; } } // 解凍後のサイズを返す return EncodeInfo.OriginalSize ; }