[問題] 替代式加密算法之解碼

[EdisonX (卡卡獸)]

這問題我常遇到，只舉一個應用當引文例子，然後請別受限在只有 256 個元素，
因其它例子的情況資料量會更大。

問題是這樣的，我必須對字串加密，加密後還必須是可視字元 ( isprint(ch)==true )，
為了加快加密之速度，我建了份 table, c約如下。

typedef unsigned char byte; ///< 因會拿來當索引，所以宣告成 unsigned char

byte enMapping[256] ;
for(i = 0 ; i < 256 ; ++i) enMapping[i] = i;
// ASCII 0x2E~0x7F 為可視字元，對這範圍做洗牌動作
shuffle(enMapping+0x2E, enMapping + (0x7F-0x2E+1) );

// 加密函式
void Encryption( byte * pszSrc , byte * pszEn , byte * enMapping)
{
    while(*pszSrc)
        *pszEn++ = enMapping[*pszSrc++];
}

解密也是一樣用 mapping 的方式進行，所以要從 byte enMapping[256] 產生出
byte deMapping[256]，目前的 Code 是直接調用 qsort , 這動作還蠻頻繁使用的，
但我覺得以這例子 "好像" 有比 qsort 還快之排序法，約如下面的方式。

void GenerateDeMapping(char * enMapping , char * deMapping)
{
    int i, j;
    byte tmpMapping[256], tmp;
    // 備份，避免把 enmapping 洗亂
    memcpy( (void*)tmpMapping , (const void*)enMapping , 256 );

    for(i = 0 ; i < 256 ; ++i) deMapping[i] = i;
    for(j = 0x2E ; j <= 0x7F ; ++j){
         // 交換到對的位置為止
        while( (tmp = tmpMapping[j]) != j) {
           swap(tmpMapping[tmp], tmpMapping[j]) ;
           swap(deMapping[tmp], deMapping[j]) ;
       }
    }
}

這裡就產生了解碼用的 mapping 了。再化簡一下問題，

Q :  假設一個整數陣列裡面，每個數字都只出現過一次，
     是否有較特殊之排序法能較快完成上述動作？ 

謝謝各位不吝賜教，感激不盡。

--

~ 這輩子與神手無緣

      我只好當神獸了 ~
                                 卡卡獸

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 180.177.74.188
→ EdisonX:還有一個問題是， byte tmpMapping[256], tmp; 這兩個變數
→ EdisonX:是不是加上 static 較佳？謝謝。
→ bibo9901:for(i=0~255) deMap[ enMap[i] ] = i;
→ EdisonX:= = 原來我把問題想複雜了, 謝謝樓上 .
推 littleshan:不要用 static，遇到 thread 會死
→ littleshan:然後如果要加密輸出可視字元，我會用 AES + Base64...
→ EdisonX:謝謝 littleshan , 我還真不知道 AES + BASE64 可編成可視
推 suhorng:base64就是anything=>可視阿..XD
→ suhorng:真正說要加密是AES
→ EdisonX:剛查了一下，真的可行，謝謝補充。
→ MOONRAKER:不會吧，上過網沒用過base64也看過base64走路
推 jackace:AEA加密後接baseXX, uuencode, QP encoding都可
推 LPH66:AES 加密後的東西拿去 QP 會不會有點太囧...
→ MOONRAKER:樓上是覺得哪裡囧 穿防彈衣後外面穿地攤外套不搭是嗎
推 LPH66:是不到不搭啦, 只是純二進位資料不太會用 QP 就是
推 jackace:用QP通常是為了保留readability 反正這用途用哪個都沒差
推 yvb:如果要求編碼前後須維持相同長度, 那 AES+Base64 就不能用了.
→ yvb:同理, 接baseXX, uuencode, QP encoding 也是一樣.
→ sardine:3樓XD
→ sardine:真是好方法
→ EdisonX:@yvb, 維持長度那問題應該不大,多一份資訊紀錄 padding
→ EdisonX:bytes 一起加密就沒問題了.