M2 渡邉くん

プロジェクト案

TODO

効率化に関するアイデアのメモ

2020/08/17TY:末尾再帰の可逆化変換の効率化 

/* original */
T_0 f(T_1 a_1, T_2 a_2, ..., T_n a_n) {
    if (e1) {
        return e2;
    } else {
        P /* return を含まないものとする */
        return f(a_1, a_2, ..., a_n);
    }
}

/* fwd S=O(n) */
T_0 f(T_1 a_1, T_2 a_2, ..., T_n a_n) {
    SAVE(0);
    while (1) {
        if (e1) {
            return e2;
        } else {
            P_fwd
            SAVE(1);
        }
    }
}

/* bwd */
void f(T_1 a_1, T_2 a_2, ..., T_n a_n) {
    RESTORE(c)
    while (c) {
        P_bwd
        RESTORE(c)
    }
}

/* fwd optimized S=O(log n) */
T_0 f(T_1 a_1, T_2 a_2, ..., T_n a_n) {
    int c = 0;
    while (1) {
        if (e1) {
            SAVE(c);
            return e2;
        } else {
            P_fwd
            c++;
        }
    }
}

/* bwd optimized */
void f(T_1 a_1, T_2 a_2, ..., T_n a_n) {
    RESTORE(c)
    while (c--) {
        P_bwd
    }
}

2020/08/18TY: swap two integer variables （→ ポインタ変数の仮引数に関する規則に一般化） 

/* original */
void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void swap_fwd(int *xp, int *yp)
{
    int temp = *xp;
    SAVE(*xp);
    *xp = *yp;
    SAVE(*yp);
    *yp = temp;
    SAVE(temp);
}

/* reversible */
void swap_rev(int *xp, int *yp)
{
    *xp ^= *yp;
    *yp ^= *xp;
    *xp ^= *yp;
}

Torbenの論文（暗号化）の例について．．． 

/* original */
T f(T_1 a_1[], ...)
{
    T_1 v_1, v_2, ...;
    ...
    a[n_i] = v_i;
    a[n_j] = v_j;
}

/* fwd optimized */
T_0 f_fwd(T_1 a_1, T_2 a_2, ..., T_n a_n) {
    T_1 ..., v_i=a[n_i], ..., v_j=a[n_j], ...;
    ...
    a[n_i] = v_i;
    ...
    a[n_j] = v_j;
}

/* bwd optimized */
T_0 f_bwd(T_1 a_1, T_2 a_2, ..., T_n a_n) {
    T_1 ..., v_i=a[n_i], ..., v_j=a[n_j], ...;
    v_j = a[n_j];
    ...
    v_i = a[n_i];
    ...
    a[n_j]=v_j;
    ...
    a[n_i]=v_i;
    ...
}

/* 適用例, さらに上書きされない局所変数はSAVEしない，厳密な規則は要検討 */
/* Mogensen T.Æ. (2019) Hermes: A Reversible Language for Writing Encryption Algorithms (Work in Progress). In: Bjørner N., Virbitskaite I., Voronkov A. (eds) Perspectives of System Informatics. PSI 2019. Lecture Notes in Computer Science, vol 11964. Springer, Cham. https://doi.org/10.1007/978-3-030-37487-7_21 */
void encrypt(uint32_t v[2], uint32_t k[4]) {
    uint32_t v0=v[0], v1=v[1], sum=0, i;           /* set up */
    uint32_t delta=0x9E3779B9;                     /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i<32; i++) {                         /* basic cycle start */
        sum += delta;
        v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
    }                                              /* end cycle */
    v[0]=v0; v[1]=v1;
}

void encrypt_fwd(uint32_t v[2], uint32_t k[4]) {
    uint32_t v0=v[0], v1=v[1], sum=0, i;           /* set up */
    uint32_t delta=0x9E3779B9;                     /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i<32; i++) {                         /* basic cycle start */
        sum += delta;
        v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
    }                                              /* end cycle */
    SAVE(sum);
    v[0]=v0; v[1]=v1;
}

void encrypt_bwd(uint32_t v[2], uint32_t k[4]) {
    uint32_t v0=v[0], v1=v[1], sum, i;
    uint32_t delta=0x9E3779B9;
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];
    RESTORE(sum);
    for (i=32; i>=0; --i) {
        v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
        v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        sum -= delta;
    }
    assert(sum==0);
    v[1]=v1;
    v[0]=v0;
}

/* encrypt_bwd は decrypt と一致することが期待される． */
void decrypt (uint32_t v[2], uint32_t k[4]) {
    uint32_t v0=v[0], v1=v[1], sum=0xC6EF3720, i;  /* set up; sum is 32*delta */
    uint32_t delta=0x9E3779B9;                     /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i<32; i++) {                         /* basic cycle start */
        v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
        v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        sum -= delta;
    }                                              /* end cycle */
    v[0]=v0; v[1]=v1;
}

UNU.RANの例に対して．．．【TBA】

参考文献など