題目簡介

值得一提的是，這道題的限時在1000ms…


輸入為N個key與plaintext的組合，輸出則為相對應的ciphertext與末尾位元取反解密得到的fliped_plaintext；

SPN密碼體系

課本樣例

問題分析

單就實作SPN加密解密演算法已有許多前輩的文章分析和代碼分析，在借鑒前輩的實作思路后發現對于下邊這種👇
再感受一下第7個樣例點的輸入資料👇

👆這樣的資料數量級以及時間要求，按照傳統的思路是無法達到1000ms的真實的，因此在群（da）友（lao）們的幫助下，通過適當的優化通過了OJ，

AC代碼

#pragma GCC optimize(3,"Ofast","inline")
#include <stdio.h>

int EnTable[65536] = {/*65536 int plaintexts in Encryption Process*/};
int DeTable[65536] = {/*65536 int plaintexts in Decryption Process*/};
// PBox and DecrySBox from textbook 3.2 example 3.1
const int DecrySBox[16] = {0xE, 0x3, 0x4, 0x8, 0x1, 0xC, 0xA, 0xF, 0x7, 0xD, 0x9, 0x6, 0xB, 0x2, 0x0, 0x5};
const int EncrySBox[16] = {0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8, 0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7};
const int PBox[16] = { 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12, 16 };
unsigned int htoi_read(void);			// hex to int Fast Read
void itoh_print(unsigned short resnum);	// int to hex Print
void SPN(void);							// Substitution-Permutation Network

int main() {
	SPN();
	return 0;
}

unsigned int htoi_read(void) { 
	int retint = 0;
	char c = getchar();
	while ((c >= 48 && c <= 57) || (c >= 97 && c <= 102)) {
		if (c >= 48 && c <= 57)retint = (retint << 4) + c - 48;
		else if (c >= 97 && c <= 102)retint = (retint << 4) + c - 87;
		c = getchar();
	}
	return retint; 
}
void itoh_print(unsigned short resnum) {	
	for (int i = 3; i >= 0; i--) {
		int c = (resnum >> (i << 2)) & 0xF;
		if (c >= 0 && c <= 9) putchar(48 + c);
		else if (c >= 10 && c <= 15) putchar(87 + c);
	}
}
void SPN(void) {
	int key, key_32bit, k1, Ntimes, tmp;
	register int plaintext;
	scanf("%d", &Ntimes);
	getchar();
	
	while (Ntimes--) {
		key_32bit = htoi_read();
		plaintext = htoi_read();
		// SPN Encryption begins
		key = key_32bit;
		// Three rounds with PermutationBox
		for (int times = 0; times < 3; ++times) {
			plaintext = EnTable[plaintext ^ ((key & 0xffff0000) >> 16)];
			key = key << 4;	
		}
		// Forth round without PermutationBox
		plaintext = plaintext ^ ((key & 0xffff0000) >> 16);
		plaintext = (plaintext << 4) | EncrySBox[(plaintext & 0xf000) >> 12];
		plaintext = (plaintext << 4) | EncrySBox[(plaintext & 0xf000) >> 12];
		plaintext = (plaintext << 4) | EncrySBox[(plaintext & 0xf000) >> 12];
		plaintext = (plaintext << 4) | EncrySBox[(plaintext & 0xf000) >> 12];
		
		key = key << 4;
		k1 = (key & 0xffff0000) >> 16;
		plaintext = plaintext ^ k1;
		
		itoh_print(plaintext);
		putchar(' ');
		// Encryption done

		// SPN Decryption begins as: last bit flips
		plaintext = plaintext ^ 0x0001;
		k1 = key_32bit;

		tmp = k1 & 0x0000ffff;
		plaintext = plaintext ^ tmp;
		k1 = k1 >> 4;
		plaintext = (plaintext << 4) | DecrySBox[(plaintext & 0xf000) >> 12];
		plaintext = (plaintext << 4) | DecrySBox[(plaintext & 0xf000) >> 12];
		plaintext = (plaintext << 4) | DecrySBox[(plaintext & 0xf000) >> 12];
		plaintext = (plaintext << 4) | DecrySBox[(plaintext & 0xf000) >> 12];

		for (int times = 0; times < 3; ++times) {
			tmp = k1 & 0x0000ffff;
			plaintext = plaintext ^ tmp;
			k1 = k1 >> 4;
			plaintext = DeTable[plaintext & 0x0000ffff];
		}
		plaintext = plaintext ^ (k1 & 0x0000ffff);

		itoh_print(plaintext);
		putchar('\n');
		// Decryption done
	}
}

優化方法

默認未優化的SPN演算法下，對于第7個樣例點的時間大概為1900ms~2000ms
（1）#pragma GCC optimize(3,"Ofast","inline")
在沒有進行其他優化時，開啟-O3、-Ofast優化，對效率有一定的提升（大概100~200ms）；

（2）使用快讀、快寫
由于第7個樣例點有4000000行輸入資料，因此采用cin/cout、scanf/printf在時間上會顯得捉襟見肘，于是采用僅次于檔案讀寫速度的getchar/putchar，完成hex to int的快讀函式與int to hex的快寫函式，才能夠應付大量的資料輸入輸出（300~500ms）；

（3）乘法運算轉換為位運算、字符運算轉換為整數運算
例如代碼中htoi_read()快讀函式中：

unsigned int htoi_read(void) { 
	int retint = 0;
	char c = getchar();
	while ((c >= 48 && c <= 57) || (c >= 97 && c <= 102)) {
		if (c >= 48 && c <= 57)retint = (retint << 4) + c - 48;
		else if (c >= 97 && c <= 102)retint = (retint << 4) + c - 87;
		c = getchar();
	}
	return retint; 
}

retint << 4即是 retint * 16（b << x 相當于 b * 2的x次方）；

retint = (retint << 4) + c - 87;相當于retint = (retint << 4) + c - 'a' + 10;；

這種優化思路的實際效果比較佛系，一定程度上取決于你提交代碼時在線OJ的心情（；

（4）加密解密程序對plaintext打表
打表的優化思路可以說是空間換時間的典型了，代碼中的int EnTable[65536]與int DnTable[65536]即為在加密程序中與解密程序中的表，可以省去大量的操作（大概300ms），

由于plaintext的長度限制為16位，因此plaintext總共的可能情況只有2 ** 16 = 65536種，根據這個條件，可以在原演算法未涉及key操作的地方，如果僅有plaintext與P盒/S盒的操作，故可以將65536種計算可能轉化為空間，再在呼叫程序中僅有一次陣列定位的時間消耗，

plaintext = EnTable[plaintext ^ ((key & 0xffff0000) >> 16)];

對于EnTable，它包括了plaintext與S盒的代換操作（原4次回圈）和P盒的置換操作（原32次回圈）；

plaintext = DeTable[plaintext & 0x0000ffff];

對于DeTable，它包括了cyphertext與S盒的4次操作（剛剛發現，AC代碼中有一部分DecryS盒的操作可以被DeTable替換）；

最后

代碼中貼不下的

int EnTable[65536] = {/*65536 int plaintexts in Encryption Process*/};
int DeTable[65536] = {/*65536 int plaintexts in Decryption Process*/};

的下載鏈接放在這里，提取碼為fele

以下是參考博客：
GCC中-O1 -O2 -O3 優化的原理是什么？
SPN實作
C++的速度優化
C++手動開啟O2優化（以及-O -O1 -O2 -O3優化的知識點）（競賽可用）