“知乎杯”2018 CCF 大学生计算机系统与程序设计竞赛 分组加密器（encryption）

#include<map>
#include<stack>
#include<vector>
#include<cstdio>
#include<iostream>
#define debug(x) cerr<<#x<<" "<<x<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int PLEN=;
const int SLEN=;
struct ptable_type{
int input_size,output_size;
int element[PLEN];
inline void Read(){
scanf("%d%d",&input_size,&output_size);
for(int i=;i<output_size;i++) scanf("%d",element+i);
}
};
struct sbox_type{
int input_size,output_size;
int element[<<SLEN];
inline void Read(){
scanf("%d%d",&input_size,&output_size);
for(int i=;i<(<<input_size);i++) scanf("%d",element+i);
}
};
struct lex_type{
string name;int type;ull value;
lex_type(string name="",int type=,ull value=):name(name),type(type),value(value){}
};
struct bs_var_type{
string name;int len;ull value;
bs_var_type(string name="",int len=,ull value=):name(name),len(len),value(value){}
vector<bs_var_type*> ch;
};
struct expr_type{
int id,type;ull value;
vector<int> bs_varp;
expr_type *expr1,*expr2;
};
struct gra_type{
int type,var,value,jmp;
vector<int> bs_varp;
expr_type* expr;
int st,ed;//lex[st] .. lex[ed]
};
int n,m;
ptable_type ptable[];
sbox_type sbox[];string code;//store all characters of the code
int loop_var[];
vector<bs_var_type> bs_var;
vector<lex_type> lex;
vector<gra_type> gra;
stack<int> loop_pos;
vector<expr_type*> expr_ptr;
void ReadPtable(){
for(int i=;i<n;i++) ptable[i].Read();
}
void ReadSbox(){
for(int i=;i<m;i++) sbox[i].Read();
}
void ReadCode(){
char ch=getchar();
while(ch!='\n') ch=getchar();
for(bool meet_end=false;;){
code+=ch=getchar();
if(ch=='D') meet_end=true;
if(ch=='L') meet_end=false;
if(ch=='\n'&&meet_end) break;
}
}
int find_bs(string &name){
for(int i=,sz=bs_var.size();i<sz;i++) if(bs_var[i].name==name) return i;
return -;
}
char type5[]={'=','+','(',')','[',']','\n'};
string type0[]={"BEGIN","END","P","S","LOOP","ENDLOOP","SPLIT","MERGE"};
void lex_ana(){
string str;lex_type tmp;
for(int i=,j,codelen=code.length();i<codelen;str.clear()){
while(code[i]==','||code[i]==' '||code[i]=='\t') i++;
str+=code[i++];
if(str[]>='A'&&str[]<='Z'){//type 0
while(i<codelen&&code[i]>='A'&&code[i]<='Z') str+=code[i++];
for(j=;j<;j++) if(str==type0[j]) break;
tmp.name=str;tmp.type=;tmp.value=j;
lex.push_back(tmp);
}
else if(str[]>='a'&&str[]<='z'){//type 1 or 2
while(i<codelen&&code[i]>='a'&&code[i]<='z') str+=code[i++];
if(str.length()==){//type 1
lex.push_back(lex_type(str,,str[]-'a'));
}
else{//type 2
j=find_bs(str);
if(j==-){
j=bs_var.size();
bs_var.push_back(bs_var_type(str,,));
}
lex.push_back(lex_type(str,,j));
}
}
else if(str[]>=''&&str[]<=''){ //type 3
while(i<codelen&&code[i]>=''&&code[i]<='') str+=code[i++];
int strl=str.length(); ull x();
for(j=;j<strl;j++) x=x*+str[j]-'';
lex.push_back(lex_type(str,,x));
}
else if(str[]=='\"'){ //type 4
while(i<codelen&&code[i]>=''&&code[i]<='') str+=code[i++];
// str+=code[i++]);
i++;
int strl=str.length();ull x=;
for(j=;j<strl;j++) x=(x<<)|str[j]-'';
lex.push_back(lex_type(str,,x));
}
else{ //type 5
for(j=;j<;j++) if(str[]==type5[j]) break;
lex.push_back(lex_type(str,,j));
}
}
}
void init_bs_var(){
for(int i=,tmp;lex[i].name!="BEGIN";i+=){
tmp=lex[i].value;
bs_var[tmp].len=lex[i+].value;
bs_var[tmp].value=;
}
}
void get_bs_var(int l,int r,ull& value,vector<int>& bs_varp){
value=lex[l].value;
for(int i=l + ;i<r;i+=){
if(lex[i+].type==) bs_varp.push_back((int)(lex[i+].value)-); // 0..25 -> -26..-1
else bs_varp.push_back(lex[i+].value); // 0..63
}
}
expr_type* generate_expr(int l,int r){
expr_type* ptr=new expr_type;
ptr->id=expr_ptr.size();
expr_ptr.push_back(ptr);
ptr->expr1=NULL;ptr->expr2=NULL;ptr->value=;
int i=l;
for(int num=;i<=r;i++){
if(lex[i].name=="(") num++;
if(lex[i].name==")") num--;
if(lex[i].name=="+"&&num==) break;
}
if(i<=r){
ptr->type=;
ptr->expr1=generate_expr(l,i-);
ptr->expr2=generate_expr(i+,r);
return ptr;
}
if(lex[l].name=="P"||lex[l].name=="S"){
if(lex[l].name=="P") ptr->type=;else ptr->type=;
if(lex[l+].type==) ptr->value=lex[l+].value-;
else if(lex[l+].type==) ptr->value=lex[l+].value;
ptr->expr1=generate_expr(l+,r-);
return ptr;
}
if(lex[l].type==){
ptr->type=;
ptr->value=lex[l].value;
return ptr;
}
if(lex[l].type==){
ptr->type=;
get_bs_var(l,r,ptr->value,ptr->bs_varp);
return ptr;
}
}
void generate_gra(int l,int r){
gra_type tmp;
tmp.st=l;tmp.ed=r;
tmp.var=tmp.value=tmp.jmp=;
tmp.expr=NULL;
if(lex[l].name=="BEGIN"){
tmp.type=tmp.value=;
}
else if(lex[l].name=="END"){
tmp.type=;
tmp.value=;
}
else if(lex[l].name=="LOOP"){
tmp.type=;
tmp.var=lex[l+].value;
tmp.value=lex[l+].value;
tmp.jmp=lex[l+].value;
loop_pos.push(gra.size());
}
else if(lex[l].name=="ENDLOOP"){
int pos=loop_pos.top();loop_pos.pop();
tmp.type=;
tmp.var=gra[pos].var;
tmp.value=gra[pos].jmp;
gra[pos].jmp=;
tmp.jmp=pos+;
}
else if(lex[l].name=="SPLIT"){
tmp.type=;
tmp.value=lex[r-].value;
ull beta;
get_bs_var(l+,r-,beta,tmp.bs_varp);
tmp.var=beta;
}
else if(lex[l].name=="MERGE"){
tmp.type=;
ull beta;
get_bs_var(l+,r-,beta,tmp.bs_varp);
tmp.var=beta;
}
else if(lex[l].type==){ //assignment statement
int i=l;
while(i<=r&&lex[i].name!="=") i++;
tmp.type=;
ull beta;
get_bs_var(l,i-,beta,tmp.bs_varp);
tmp.var=beta;
tmp.expr=generate_expr(i+,r-);
}
gra.push_back(tmp);
}
void gra_ana(){
int i=,j,sz=lex.size();
for(i=;lex[i].name!="BEGIN";i++);
for(;i<sz;i=j+){
for(j=i;lex[j].name!="\n";j++);
generate_gra(i,j);
}
}
void bs_to_num(const string& str,ull& num){
num=;
for(int i=,sz=str.length();i<sz;i++) num=(num<<)|str[i]-'';
}
void num_to_bs(const ull& num,string& str,int size=PLEN){
str.clear();
for(ull tmp=1ull<<size-;tmp;tmp>>=) if(num&tmp) str+='';else str+='';
}
string int_to_str(int i){
string str;
stack<char>s;
if(i==){str="";return str;}
if(i<) str+='-',i=-i;
for(;i>;i/=) s.push((i%)+'');
while(!s.empty()) str+=s.top(),s.pop();
return str;
}
bs_var_type* find_bs_varp(ll pos,const vector<int>& bs_varp){
bs_var_type* ptr=&bs_var[pos];//?????
for(int i=,sz=bs_varp.size();i<sz;i++){
int j=bs_varp[i];
if(j<) j=loop_var[j+];
ptr=ptr->ch[j];
}
return ptr;
}
ull cal_expr(expr_type* ptr){
if(ptr->type==) return find_bs_varp(ptr->value,ptr->bs_varp)->value;
else if(ptr->type==) return ptr->value;
else if(ptr->type==) return cal_expr(ptr->expr1)^cal_expr(ptr->expr2);
else if(ptr->type==){
ull tmp=cal_expr(ptr->expr1);
ll j=ptr->value;
if(j<) j=loop_var[j+];
string sin,sout;
num_to_bs(tmp,sin,ptable[j].input_size);
for(int i=;i<ptable[j].output_size;i++)
sout.push_back(sin[ptable[j].element[i]]);
bs_to_num(sout,tmp);
return tmp;
}
else if(ptr->type==){
ull tmp=cal_expr(ptr->expr1);
ll j=ptr->value;
if(j<) j=loop_var[j+];
return sbox[j].element[tmp];
}
}
ull encrypt(ull state,ull key){
for(int now=;;){
if(gra[now].type==){
if(gra[now].value==){ //BEGIN
bs_var[].value=state;
bs_var[].value=key;
for(int i=;i<bs_var.size();i++) bs_var[i].value=;
now++;
}
else return bs_var[].value; //END
}
else if(gra[now].type==){
bs_var_type* ptr=find_bs_varp(gra[now].var,gra[now].bs_varp);
ptr->value=cal_expr(gra[now].expr);
now++;
}
else if(gra[now].type==){
loop_var[gra[now].var]=gra[now].value;
now++;
}
else if(gra[now].type==){
loop_var[gra[now].var]++;
if(loop_var[gra[now].var]>gra[now].value) now++;
else now=gra[now].jmp;
}
else if(gra[now].type==){
bs_var_type* ptr=find_bs_varp(gra[now].var,gra[now].bs_varp);
int tmp=gra[now].value;
int chlen=ptr->len / tmp;
for(int i=;i<tmp;i++){
bs_var_type* chptr=new bs_var_type;
chptr->len=chlen;
chptr->name=ptr->name+"["+int_to_str(i)+"]";
chptr->value=;
ptr->ch.push_back(chptr);
}
ull beta=(1ull<<chlen)-;
for(int i=tmp-;~i;i--){
ptr->ch[i]->value=ptr->value & beta;
ptr->value=ptr->value>>chlen;
}
now++;
}
else if(gra[now].type==){
bs_var_type* ptr=find_bs_varp(gra[now].var,gra[now].bs_varp);
int tmp=ptr->ch.size();
int chlen=ptr->len / tmp;
ptr->value=;
for(int i=;i<tmp;i++){
bs_var_type* chptr=ptr->ch[i];
ptr->value=(ptr->value<<chlen)|chptr->value;
delete chptr;
}
ptr->ch.clear();
now++;
}
}
}
void InitTaskA(){
scanf("%d%d",&n,&m);
ReadPtable();
ReadSbox();
ReadCode();
}
void SolveTaskA(){
lex_ana();
init_bs_var();
gra_ana();
int k; ull state,key; string str1,str2;
scanf("%d",&k);
for(int i=;i<k;i++){
cin>>str1>>str2;
bs_to_num(str1,state);
bs_to_num(str2,key);
num_to_bs(encrypt(state,key),str1,bs_var[].len);
puts(str1.c_str());
}
}
void taskB_init(){
code="state(32)\n";
code += "key(12)\n";
code += "dkey(16)\n";
code += "tmp(32)\n";
code += "BEGIN\n";
code += "SPLIT(dkey,4)\n";
code += "SPLIT(key,3)\n";
code += "dkey[0]=key[0]\n";
code += "dkey[1]=key[1]\n";
code += "dkey[2]=key[2]\n";
code += "dkey[3]=key[0] + key[1] + key[2]\n";
code += "MERGE(key)\n";
code += "MERGE(dkey)\n";
code += "LOOP i 1 16\n";
code += "dkey=P[2](dkey)\n";
code += "tmp=state\n";
code += "SPLIT(state,2)\n";
code += "SPLIT(tmp,2)\n";
code += "state[0]=tmp[1]\n";
code += "tmp[1]=tmp[1] + dkey\n";
code += "SPLIT(tmp[1],4)\n";
code += "LOOP j 0 3\n";
code += "tmp[1][j]=S[0](tmp[1][j])\n";
code += "ENDLOOP\n";
code += "MERGE(tmp[1])\n";
code += "state[1]=tmp[0] + P[0](tmp[1])\n";
code += "MERGE(state)\n";
code += "MERGE(tmp)\n";
code += "dkey=P[1](dkey)\n";
code += "ENDLOOP\n";
code += "tmp=state\n";
code += "SPLIT(state,2)\n";
code += "SPLIT(tmp,2)\n";
code += "state[0]=tmp[1]\n";
code += "state[1]=tmp[0]\n";
code += "MERGE(state)\n";
code += "MERGE(tmp)\n";
code += "END\n";
n=;
m=;
ptable[].input_size=;
ptable[].output_size=;
ptable[].input_size=;
ptable[].output_size=;
ptable[].input_size=;
ptable[].output_size=;
sbox[].input_size=;
sbox[].output_size=;
int p0[]={, , , , , , , , , , , , , , , };
int p1[]={, , , , , , , , , , , , , , , };
int p2[]={, , , , , , , , , , , , , , , };
int s0[]={, , , , , , , , , , , , , , , };
for(int i=;i<;i++){
ptable[].element[i]=p0[i];
ptable[].element[i]=p1[i];
ptable[].element[i]=p2[i];
sbox[].element[i]=s0[i];
}
}
void solve_taskB(){
lex_ana();
init_bs_var();
gra_ana();
ull state, ans, tmp;
string str1, str2;
int key1,key2;
map<ull,int> h;
cin >> str1 >> str2;
bs_to_num(str1,state);
bs_to_num(str2,ans);
for(int i=;i<;i++){
tmp=encrypt(state,i);
h[tmp]=i;
}
int p1[]={, , , , , , , , , , , , , , , };
int p2[]={, , , , , , , , , , , , , , , };
for(int i=;i<;i++){
ptable[].element[i]=p1[i];
ptable[].element[i]=p2[i];
}
for(int i=;i<;i++){
tmp=encrypt(ans,i);
if(h.find(tmp)==h.end()) continue;
key1=h[tmp];
key2=i;
num_to_bs(key1,str1,);
num_to_bs(key2,str2,);
cout << "YES" << endl;
cout << str1 << endl;
cout << str2 << endl;
return;
}
cout << "NO" << endl;
}
char task_id[];
int main(){
freopen("encryption.in","r",stdin);
freopen("encryption.out","w",stdout);
scanf("%s",task_id);
if(task_id[]=='A'){
InitTaskA();
SolveTaskA();
}
else{
// puts("NO");//pass 3 points
taskB_init();
solve_taskB();
}
fclose(stdin);fclose(stdout);
return ;
}