Как побороть двойную свободную или коррупцию (out) Aborted (core dumped) в c

Question

Я пытаюсь создать функцию zoom_image, которая увеличивает серое изображение с помощью дискретного преобразования Фурье.код, который я включаю, работает, если размер изображения меньше или равен 4 * 4, но если размер увеличивается.он выдает ошибку 'double free,

#include<math.h>
#include<stdio.h>
#include<stdlib.h>
struct complex{
      float real;
      float im;
};
typedef struct complex complex;
complex w(int i, int n) {
      complex result;
      result.real = cos(2*M_PI*i/n);
      result.im = -sin(2*M_PI*i/n);
      return result;
}
complex wp(int i, int n) {
      complex result;
      result.real = cos(2*M_PI*i/n);
      result.im = sin(2*M_PI*i/n);
      return result;
}
complex mul(complex a, complex b) {
      complex result;
      result.real = a.real*b.real - a.im*b.im;
      result.im = a.real*b.im + b.real*a.im;
      return result;
}
complex divi(complex a, complex b) {
      complex result;
      result.real = (a.real*b.real + a.im*b.im)/(b.real*b.real + b.im*b.im);
      result.im = (-a.real*b.im + b.real*a.im)/(b.real*b.real + b.im*b.im);
      return result;
}
complex add(complex a, complex b) {
      complex result;
      result.real = a.real+b.real ;
      result.im = a.im+b.im;
      return result;
}
complex sub(complex a, complex b) {
      complex result;
      result.real = a.real - b.real;
      result.im = a.im - b.im;
      return result;
}
void printComplex(complex var) {
      printf("%f i%f\n",var.real,var.im);
}
void printComplexS(complex var) {
      printf("%f i%f",var.real,var.im);
}

#include<stdio.h>
#include<stdlib.h>
#include"complex.h"
static int gb=0;
complex* _fft(complex *arr, int size, int step, int index) {
    if(size == 2) {
        complex *result;
        result = (complex*)malloc(size*sizeof(complex));
        result[0] = add(arr[index], arr[index+step]);
        result[1] = sub(arr[index], arr[index+step]);
        return result;
    }
    else {
        int i;
        complex *even, *odd, *result, *mull;
        even = _fft(arr, size/2, step*2, index);
        odd = _fft(arr, size/2, step*2, index+step);
        result = (complex*)malloc(size*sizeof(complex));
        mull = (complex*)malloc(size/2*sizeof(complex));
        for(i=0;i<size/2;i++) {
            mull[i] = mul(odd[i], w(i,size));
        }
        for(i=0;i<size/2;i++)
            result[i] = add(even[i], mull[i]);
        for(;i<size;i++)
            result[i] = sub(even[i - size/2], mull[i - size/2]);
        free(even);
        free(odd);
        free(mull);
        return result;
    }
}
complex* fft(complex *arr, int size) {
      return (complex*)_fft(arr, size, 1, 0);
}
complex* _ifft(complex *arr, int size, int step, int index) {
      if(size == 2) {
            complex *result;
            result = (complex*)malloc(size*sizeof(complex));
            result[0] = add(arr[index], arr[index+step]);
            result[1] = sub(arr[index], arr[index+step]);
            return result;
      }
      else {
            int i;
            complex *even, *odd, *result, *mull;
            even = _ifft(arr, size/2, step*2, index);
            odd = _ifft(arr, size/2, step*2, index+step);
            result = (complex*)malloc(size*sizeof(complex));
            mull = (complex*)malloc(size/2*sizeof(complex));
            for(i=0;i<size/2;i++)
                  mull[i] = mul(odd[i], wp(i,size));
            for(i=0;i<size/2;i++)
                  result[i] = add(even[i], mull[i]);
            for(;i<size;i++)
                  result[i] = sub(even[i - size/2], mull[i - size/2]);
            free(even);
            free(odd);
            free(mull);
            return result;
      }
}
complex* ifft(complex *arr, int size) {
    complex *re = _ifft(arr, size, 1, 0);
    for(int i=0;i<size;i++){
        re[i].real=re[i].real/size;
        re[i].im=re[i].im/size;
    }
    return re;
}
complex** transpose(complex **src, int n, int m) {
    complex **result, ***re;
    result=(complex**)malloc(sizeof(complex*)*m);
    for(int i=0;i<m;i++) {
        result[i]=(complex*)malloc(sizeof(complex)*n);
        for(int j=0;j<n;j++)
            result[i][j]=src[j][i];
    }
    re=(complex***)&result;
    return (complex**)*re;
}
complex** fft_2d(complex** arr, int n, int m) {
    complex **arrR, ***r, *temp;
    int i, j;
    arrR = (complex**)malloc(sizeof(complex*));
    for(i=0;i<n;i++) {
        arrR[i]=(complex*)fft(arr[i],m);
        printf("%d ",i);
    }
    arrR=(complex**)transpose(arrR,n,m);
    malloc(0);
    for(i=0;i<m;i++)
        arrR[i]=(complex*)fft(arrR[i],n);
    arrR=transpose(arrR,n,m);
    r=(complex***)&arrR;
    return (complex**)*r;
}
complex** ifft_2d(complex** arr, int n, int m) {
    complex **arrR, ***r, *temp;
    int i, j;
    arrR = (complex**)malloc(sizeof(complex*));
    for(i=0;i<n;i++)
        arrR[i]=(complex*)ifft(arr[i],m);
    arrR=(complex**)transpose(arrR,n,m);
    malloc(0);
    for(i=0;i<m;i++)
        arrR[i]=(complex*)ifft(arrR[i],n);
    arrR=transpose(arrR,n,m);
    r=(complex***)&arrR;
    return (complex**)*r;
}

unsigned int** zoom_img(unsigned int **img, int col, int row, int r_col, int r_row) {
    int i, j;
    complex **mat=(complex**)malloc(sizeof(complex*)*col), **re;
    complex **new_re=(complex**)malloc(sizeof(complex*)*(col+2*r_col)), **u;
    unsigned int **result=(unsigned int**)malloc(sizeof(unsigned int*)*(col + 2*r_col)), ***z;
    for(i=0;i<col;i++)
        mat[i]=(complex*)malloc(sizeof(complex)*row);
    for (i=0;i<col;i++) {
        for (j=0;j<row;j++) {
            mat[i][j].real = (float)pow(-1, i+j)*(float)img[i][j];
            mat[i][j].im=0;
        }
    }
    re = (complex**)fft_2d(mat, col, row);
    for(i=0;i<(col+2*r_col);i++)
        new_re[i]=(complex*)malloc(sizeof(complex)*(row+2*r_row));
    for(i=0;i<(col+2*r_col);i++) {
        for(j=0;j<(row+2*r_row);j++) {
            if(i<r_col || i>r_col+col-1 || j<r_row || j>r_row+row-1) {
                new_re[i][j].real = 0;
                new_re[i][j].im = 0;
            }
            else
                new_re[i][j]=re[i-r_col][j-r_row];
        }
    }
    u = (complex**)ifft_2d(new_re, col+2*r_col, row + 2*r_row);
    for(i=0;i<(col+2*r_col);i++) {
        result[i]=(unsigned int*)malloc(sizeof(unsigned int)*(row+2*r_row));
        for(j=0;j<(row+2*r_row);j++) {
            result[i][j] = (unsigned int)u[i][j].real;
        }
    }
    z=&result;
    return *z;
}

int main() {
    unsigned int i, j, **arr=(unsigned int**)malloc(sizeof(unsigned int*)*2), **result;
    for(i=0;i<2;i++) {
        arr[i]=(unsigned int*)malloc(sizeof(unsigned int)*2);
        for(j=0;j<2;j++) {
             arr[i][j] = i+j +1;
        }
    }
    result = zoom_img(arr,2,2,2,2);
    return 0;
}/*
int main() {
    complex **arr, **result, **re;
    arr=(complex**)malloc(sizeof(complex*)*4);
    for (int i = 0; i < 4; i++) {
        arr[i]=(complex*)malloc(sizeof(complex)*4);
        for (int j = 0; j < 4; j++) {
            arr[i][j].real = i*j+1.2;
            arr[i][j].im=0;
        }
    }
    result = (complex**)fft_2d(arr,4,4);
    //malloc(0);
    re = (complex**)ifft_2d(result,4,4);
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            printf("(%2f) ", arr[i][j].real);
            printComplexS(result[i][j]);
            printf(" (%2f) ",re[i][j].real);
        }
        printf("\n");
    }
      return 0;
}*/

Answer 1

Код имеет несколько проблем.

complex** ifft_2d(complex** arr, int n, int m) {
    complex **arrR, ***r;
    int i;

И тогда вы выделяете слишком мало:

    arrR = (complex**)malloc(sizeof(complex*));

Строка выше должна быть malloc(sizeof(complex*) * n).Без *n следующая строка вызывает неопределенное поведение (переполнение буфера):

    for(i=0;i<n;i++)
        arrR[i]=(complex*)ifft(arr[i],m);

Тогда есть эта странная строка, зачем она?

    malloc(0);

Тогда окончаниефункция странная (почему бы просто не вернуть arrR?):

    r=(complex***)&arrR;
    return (complex**)*r;

Далее, рекурсивный код (_ifft и _fft) предполагает, что size является степенью двойки, в противном случае он попадает в бесконечную рекурсию.Вы должны подтвердить ввод.По крайней мере, утверждайте, что:

assert(n >= 2);
assert(((n-1) & n ) == 0); // for positive n, assert that it is a power of 2

С этой строкой вы можете увидеть, что zoom_img нарушает это предположение в строке:

u = (complex**)ifft_2d(new_re, col+2*r_col, row + 2*r_row);

Обратите внимание, что в нескомментированном main, col== 2, строка == 2, r_col == 2, r_row == 2, которая заканчивается размером == 6, который не является степенью 2.

Меньшая проблема связана с производительностью.Код перебирает malloc вместо повторного использования одного и того же блока памяти и заглядывает в разные его области.Это то, что делает классический БПФ.Классическое БПФ также не использует рекурсию подобным образом, но вместо этого использует итерации.