Harigami
ログイン
1
anonymous FFTによる多項式の乗算
Public Domain C
#include <complex.h>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef double complex cmplx;

int exp_table[] = {
    1,
    2,
    4,
    8,
    16,
    32,
    64,
    128,
    256,
    512,
    1024,
    2048,
    4096,
    8192,
    16384,
    32768,
    65536,
    131072,
    262144,
    524288,
    1048576,
    2097152,
    4194304,
    8388608,
    16777216,
    33554432,
    67108864,
    134217728,
    268435456,
    536870912,
    1073741824,
};

cmplx omega(int k, int v) {
    return cexp(-v * 2 * M_PI * I / exp_table[k]);
}

int find_next_power(int n) {
    // ループカウンタ
    int i;

    for(i = 0; i < 32; i++) {
        if(n <= exp_table[i]) return i;
    }

    return -1;
}

// 2^k個の領域を確保
cmplx *alloc_fourier(int k) {
    cmplx *result;

    result = malloc(sizeof(cmplx) * exp_table[k]);

    return result;
}

void output_cmplx_array(const cmplx *eA, int k) {
    // ループカウンタ
    int i;

    for(i = 0; i < exp_table[k]; i++) {
        printf("%f+%f\n", creal(eA[i]), cimag(eA[i]));
    }
}

// A: 変換対象の配列
// k: 次数
// 次数を1ずつ下げながらDFTを行なう
void fftr(cmplx *A, int k) {
    // feとfo
    cmplx *fe, *fo;
    // ループカウンタ
    int i;

    if(k <= 0) return;

    // feとfoを確保する
    fe = alloc_fourier(k-1);
    fo = alloc_fourier(k-1);

    // feとfoに値を詰め込む
    for(i = 0; i < exp_table[k-1]; i++) {
        fe[i] = A[i*2];
        fo[i] = A[i*2+1];
    }

    // 再帰フーリエ変換
    fftr(fe, k-1);
    fftr(fo, k-1);

    // 上書き
    for(i = 0; i < exp_table[k-1]; i++) {
        A[i] = fe[i] + omega(k, i) * fo[i];
        A[i + exp_table[k-1]] = fe[i] - omega(k, i) * fo[i];
    }

    // 解放する
    free(fe);
    free(fo);
}

void conj_array(cmplx *A, int k) {
    // ループカウンタ
    int i;

    // 共役をとる
    for(i = 0; i < exp_table[k]; i++) {
        A[i] = conj(A[i]);
    }
}

void mult_array(const cmplx *A, const cmplx *B, cmplx *C, int k) {
    // ループカウンタ
    int i;

    // 乗算する
    for(i = 0; i < exp_table[k]; i++) {
        C[i] = A[i] * B[i];
    }
}

void ifft(cmplx *A, int k) {
    // ループカウンタ
    int i;
    // 共役をとる
    conj_array(A, k);
    // fft
    fftr(A, k);
    // 共役をとる
    conj_array(A, k);

    // わる
    for(i = 0; i < exp_table[k]; i++) A[i] /= exp_table[k];
}

void copy_int_to_cmplx(const int *A, cmplx *eA, int n) {
    // ループカウンタ
    int i;

    for(i = 0; i < n; i++) eA[i] = A[i];
}


void convolve(const int *A, const int *B, int *C, int n) {
    // 拡張されたA, B
    cmplx *eA, *eB;
    // 畳み込みの結果
    cmplx *eC;
    // n * 2のパワー
    int power = find_next_power(n * 2);
    // 拡張された長さ
    int eLen = exp_table[power];
    // ループカウンタ
    int i;

    // eA, eB, eCを確保,初期化
    eA = malloc(sizeof(cmplx) * eLen);
    eB = malloc(sizeof(cmplx) * eLen);
    eC = malloc(sizeof(cmplx) * eLen);
    memset(eA, 0, sizeof(cmplx) * eLen);
    memset(eB, 0, sizeof(cmplx) * eLen);
    copy_int_to_cmplx(A, eA, n);
    copy_int_to_cmplx(B, eB, n);

    // 巡回畳込みを行なう
    fftr(eA, power);
    fftr(eB, power);
    mult_array(eA, eB, eC, power);
    ifft(eC, power);


    // 結果をCに書き戻す
    for(i = 0; i < n * 2 - 1; i++) {
        C[i] = round(creal(eC[i]));
    }

    // eA, eB, eCを解放
    free(eA);
    free(eB);
    free(eC);
}

void input_array(int *A, int n) {
    // ループカウンタ
    int i;

    for(i = 0; i < n; i++) scanf("%d", A + i);
}

void output_array(const int *C, int n) {
    // ループカウンタ
    int i;
    
    for(i = 0; i < n; i++) printf("%d\n", C[i]);
}

int main(void) {
    // 多項式の次数
    int n;
    // 入力、出力の配列サイズ
    int isize, osize;
    // 入力配列
    int *A, *B;
    // 出力配列
    int *C;
    // ループカウンタ
    int i;

    scanf("%d", &n);
    isize = n + 1;
    osize = (n + 1) * 2 - 1;

    // nに応じてA, Bを確保
    A = malloc(sizeof(int) * isize);
    B = malloc(sizeof(int) * isize);

    // 値を入力
    for(i = 0; i < isize; i++) {
        scanf("%d", A + i);
        scanf("%d", B + i);
    }

    // nに応じてCを確保
    C = malloc(sizeof(int) * osize);

    // 畳み込みを行なう
    convolve(A, B, C, isize);

    // 出力
    output_array(C, osize);

    // 全て解放
    free(A);
    free(B);
    free(C);

    return 0;
}

  • 0
  • 0
anonymous タイトルなし
C
💩
  • 0
  • 0
anonymous タイトルなし
C
#include <openssl/des.h>
#include <sys/time.h> // For time measures
#include <string.h>
#include <ctype.h>

// Encryption/Decryption switches
#define ENC 1
#define DEC 0

// From char to DES_LONG (be aware that c is shifted)
// char→DES型
#define c2l(c,l)    (l =((DES_LONG)(*((c)++))), \
                     l|=((DES_LONG)(*((c)++)))<< 8L, \
                     l|=((DES_LONG)(*((c)++)))<<16L, \
                     l|=((DES_LONG)(*((c)++)))<<24L)

// From DES_LONG to char (be aware that c is shifted)
// DES→char
#define l2c(l,c)	(*((c)++)=(unsigned char)(((l)     )&0xff), \
                     *((c)++)=(unsigned char)(((l)>> 8L)&0xff), \
                     *((c)++)=(unsigned char)(((l)>>16L)&0xff), \
                     *((c)++)=(unsigned char)(((l)>>24L)&0xff))

void write_output(const char *filename, const unsigned char *in)
{
    // Now... Open the file binary with writing capabilities
    FILE *fp = fopen(filename, "wb");

    // If it can't be open, then return an error message
    if (fp == NULL) {fputs ("File error", stderr); exit (1);}

    // Write the in-array to specificed file-location
    fwrite(in, sizeof(unsigned char), strlen((const char *)in), fp);

    // Close the it
    fclose(fp);
}

const unsigned char *read_inputtext(const char *filename)
{
    // Total number of bytes
    unsigned long fsize;

    // Result of reading the file
    size_t result;

    // Now... Open the file binary with reading capabilities
    FILE *fp = fopen(filename, "rb");

    // If it can't be open, then return an error message
    if (fp == NULL) {fputs ("File error",stderr); exit (1);}

    /* Find out the number of bytes */
    fseek(fp, 0, SEEK_END);
    fsize = ftell(fp);      /* Get the size of the file */
    rewind(fp);             /* Go back to the start */

    // Allocate the buffer + 1 for termination
    unsigned char* buffer = malloc(fsize * sizeof *buffer + 1);

    // Test that everything went as we expected
    if(buffer == NULL) { fputs("Memory error!", stderr); exit(2); }

    // Read the buffer
    result = fread(buffer, 1, fsize * sizeof *buffer, fp);

    // Something went wrong when we read the file; sizes to not match
    if (result != fsize) {fputs ("Reading error", stderr); exit (3);}

    // Terminate the str
    buffer[fsize] = '\0';

    // Close the file
    fclose(fp);

    // Return the pointer to the dynamic allocated array
    return buffer;
}

void str2DES_cblock(const char *str, DES_cblock *out)
{
    // Make a char pointer and point it at the start of the array
    unsigned char *o;
    o = out[0];

    // Read the string
    int i;
    for (i = 0; i < 8; i++)
        sscanf(&(str[i*2]),"%2hhx", o++);
}

void my_des_cbc_encrypt(unsigned char *input, unsigned char *output, long length, DES_key_schedule ks, DES_cblock *ivec, int env){
  /*
    Assume that the input length (in byte) is a multiple of 8
    Try to undestand the macros l2c and c2l. They are important in implementation of CBC
    入力は8の倍数byte
  */

  unsigned char *iv;            // Initialization vector
  long l = length;

  DES_LONG xor0, xor1;
  DES_LONG in0, in1;
  DES_LONG data[2];
  /*
     Addtional variables
  */

  iv = ivec[0];

  //Initialize XOR-variables
  c2l(iv, xor0);
  c2l(iv, xor1);

  //Handling 8 bytes of input data each time inside the for loop.
  for(l = -8; l >= 0; l = -8){
    /*
      Your implementation of DES in CBC mode.
      Using des_encrypt1().
    */
    
  }
}

int main(int argc, char *argv[])
{
    int k;
    des_key_schedule key;
    DES_cblock iv, cbc_key;

    /*
      Other variables
    */
    const unsigned char *in;
    unsigned char *inp,*out;
    unsigned char *des_out;
    long s;
    FILE *fp; // ファイルポインタの作成
    char ch;
    char str[256];
    //DES_cblock in,out;
    /*
      Check number of command line arguments
    */
    if(argc != 5){
      printf("Not enough or too many arguments!\n");
      exit(1);
    }

    /*
      Check key and initialization vector validities. (comprise of Hexadicimal digits or not)
    */
    //16進数かを判定する関数
    if(isxdigit(*argv[1])!=1 || isxdigit(*argv[2])!=1) {
      if(isxdigit(*argv[1])!=1) printf("iv is not hexadecimal.\n");
      if(isxdigit(*argv[2])!=1) printf("key is not hexadecimal.\n");
      exit(2);
    }
    /*
      Convert key and initialization vector from string to DES_cblock
    */
    str2DES_cblock(argv[1],&iv);
    str2DES_cblock(argv[2],&cbc_key);
    //str2DES_cblock(argv[3],&in);
    //str2DES_cblock(argv[4],&out);
    /*
      read_inputtext();
    */
    fp = fopen(argv[3],"r");
    while(fgets(str, 256, fp) != NULL) {}
    fclose(fp);
    s = strlen(str) - 1;

    in = read_inputtext(argv[3]);
    inp = in;
    printf("%s",inp);

    /*
      my_des_cbc_encrypt();
    */

    //void my_des_cbc_encrypt(unsigned char *input, unsigned char *output, long length, DES_key_schedule ks, DES_cblock *ivec, int env){
    //my_des_cbc_encrypt(inp,out,s,key,&iv,ENC);
    //printf("%s\n", out);
    /*
      write_output();
    */
    //write_output(argv[4],x);

    //Compare the resutl with that using built-in funtion des_cbc_encrypt(). Details of des_cbc_encrypt() can be seen at http://web.mit.edu/macdev/Development/MITKerberos/MITKerberosLib/DESLib/Documentation/api.html
    /*
      des_cbc_encrypt();
    */
    des_cbc_encrypt(in,out,s,key,&iv,ENC);

    /*
     Print out ciphertexts from  my_des_cbc_encrypt() and  des_cbc_encrypt() to compare
    */
    printf("Plain text: ");
    fp = fopen(argv[3],"r");
    while( ( ch = fgetc(fp) ) != EOF ) {
      printf("%c", ch);
    }
    //printf("\n");
    fclose(fp);

    printf("Cipher text: ");
    fp = fopen(argv[4],"r");
    while( ( ch = fgetc(fp) ) != EOF ) {
      printf("%c", ch);
    }
    printf("\n");
    fclose(fp);

    return 0;
}
  • 0
  • 0
あなたもコードを投稿しませんか?
投稿する
1