main.c

#include <stdio.h>
#include <stdlib.h>

// Usado struct para otimização do código
// Guarda as informações RGB de cada pixel da matriz
typedef struct rgb{
    int cor[3];
}rgb;

rgb **alocaMatriz(int tam);
void liberaMatriz(rgb **matriz, int tam);
void leMatriz(rgb **matriz, int tam, int valorCor);
void imprimeMatriz(rgb **matriz, int tam, int valorCor);
void multiplicaMatriz(rgb **matrizA, rgb **matrizB, rgb **matrizResult, int tam, int valorCor);
rgb **somaMatriz (rgb **primeiraParte, rgb **segundaParte, int tam, int valorCor);
rgb **subtraiMatriz (rgb **primeiraParte, rgb **segundaParte, int tam, int valorCor);
void divideMatrizStrassen(rgb **matriz, rgb **quadranteA, rgb **quadranteB, rgb **quadranteC, rgb **quadranteD, int tam, int valorCor);
rgb **algoritmoStrassen (rgb **matrizPixel, rgb **matrizFiltro, int tam, int valorCor);

int main() {
    char formato[3];
    int n;
    int corMax;
    const int valorCor = 3;

    fgets(formato, sizeof(formato), stdin);
    scanf("%d %d", &n, &n);
    scanf("%d", &corMax);

    // Manipulação das matrizes
    rgb **matrizPixel = alocaMatriz(n);
    leMatriz(matrizPixel, n, valorCor);
    rgb **matrizFiltro = alocaMatriz(n);
    leMatriz(matrizFiltro, n, valorCor);

    rgb **matrizResult = algoritmoStrassen(matrizPixel, matrizFiltro, n, valorCor);

    // Output
    printf("%s\n", formato);
    printf("%d %d\n", n, n);
    printf("%d", corMax);
    imprimeMatriz(matrizResult, n, valorCor);

    liberaMatriz(matrizPixel, n);
    liberaMatriz(matrizFiltro, n);
    liberaMatriz(matrizResult, n);
    return 0;
}

// Funções
rgb **alocaMatriz(int tam) {
    rgb **matriz = malloc(sizeof(rgb *) * tam);
    for (int i = 0; i < tam; i++)
        matriz[i] = malloc(sizeof(rgb) * tam);
    return matriz;
}

void liberaMatriz(rgb **matriz, int tam) {
    for (int i = 0; i < tam; i++)
        free(matriz[i]);
    free(matriz);
}

void leMatriz(rgb **matriz, int tam, int valorCor) {
    for (int i = 0; i < tam; i++) {
        for (int j = 0; j < tam; j++) {
            for (int k = 0; k < valorCor; k++) {
                scanf("%d", &matriz[i][j].cor[k]);
            }
        }
    }
}

void imprimeMatriz(rgb **matriz, int tam, int valorCor) {
    for (int i = 0; i < tam; i++) {
        printf("\n");
        for (int j = 0; j < tam; j++) {
            for (int k = 0; k < valorCor; k++) {
                printf("%d ", matriz[i][j].cor[k]);
            }
        }
    }
}

// Multiplicação clássica de matriz para o caso base
void multiplicaMatriz(rgb **matrizA, rgb **matrizB, rgb **matrizResult, int tam, int valorCor) {
    for (int i = 0; i < tam; i++) {
        for (int j = 0; j < tam; j++) {
            for (int k = 0; k < valorCor; k++) {
                matrizResult[i][j].cor[k] = 0;
            }
            for (int l = 0; l < tam; l++) {
                for (int k = 0; k < valorCor; k++) {
                    matrizResult[i][j].cor[k] += matrizA[i][l].cor[k] * matrizB[l][j].cor[k];
                }
            }
        }
    }
}

// Funções para o strassen
rgb **somaMatriz (rgb **primeiraParte, rgb **segundaParte, int tam, int valorCor) {
    rgb **result = alocaMatriz(tam);
    for (int i = 0; i < tam; i++) {
        for (int j = 0; j < tam; j++) {
            for (int k = 0; k < valorCor; k++) {
                result[i][j].cor[k] = primeiraParte[i][j].cor[k] + segundaParte[i][j].cor[k];
            }
        }
    }
    return result;
}

rgb **subtraiMatriz (rgb **primeiraParte, rgb **segundaParte, int tam, int valorCor) {
    rgb **result = alocaMatriz(tam);
    for (int i = 0; i < tam; i++) {
        for (int j = 0; j < tam; j++) {
            for (int k = 0; k < valorCor; k++) {
                result[i][j].cor[k] = primeiraParte[i][j].cor[k] - segundaParte[i][j].cor[k];
            }
        }
    }
    return result;
}

// Divide a matriz em quatro quadrantes (submatrizes)
void divideMatrizStrassen(rgb **matriz, rgb **quadranteA, rgb **quadranteB, rgb **quadranteC, rgb **quadranteD, int tam, int valorCor) {
    //  Formato depois da divisão:
    //  | A   B |
    //  | C   D |
    //  Cada quadrante copia os elementos de sua determinada região
    for (int i = 0; i < tam; i++) {
        for (int j = 0; j < tam; j++) {
            for (int k = 0; k < valorCor; k++) {
                quadranteA[i][j].cor[k] = matriz[i][j].cor[k];
                quadranteB[i][j].cor[k] = matriz[i][j + tam].cor[k];
                quadranteC[i][j].cor[k] = matriz[i + tam][j].cor[k];
                quadranteD[i][j].cor[k] = matriz[i + tam][j + tam].cor[k];
            }
        }
    }
}

rgb **algoritmoStrassen (rgb **matrizPixel, rgb **matrizFiltro, int tam, int valorCor) {
    rgb **matrizRes = alocaMatriz(tam);
    // Caso base:
    // Como avisado no trabalho, seria mais eficiente em matrizes de 64x64 ou menores serem resolvidas pela multiplicação tradicional.
    if (tam < 64) {
        multiplicaMatriz(matrizPixel, matrizFiltro, matrizRes, tam, valorCor);
        return matrizRes;
    }

    int novoTamanho = (tam/2);

    rgb **quadranteA = alocaMatriz(novoTamanho);
    rgb **quadranteB = alocaMatriz(novoTamanho);
    rgb **quadranteC = alocaMatriz(novoTamanho);
    rgb **quadranteD = alocaMatriz(novoTamanho);
    divideMatrizStrassen(matrizPixel, quadranteA, quadranteB, quadranteC, quadranteD, novoTamanho, valorCor);

    rgb **quadranteE = alocaMatriz(novoTamanho);
    rgb **quadranteF = alocaMatriz(novoTamanho);
    rgb **quadranteG = alocaMatriz(novoTamanho);
    rgb **quadranteH = alocaMatriz(novoTamanho);
    divideMatrizStrassen(matrizFiltro, quadranteE, quadranteF, quadranteG, quadranteH, novoTamanho, valorCor);

    // Produtos de Strassen
    rgb **P1, **P2, **P3, **P4, **P5, **P6, **P7;

    // P1 = A.(F-H)
    P1 = algoritmoStrassen(quadranteA, subtraiMatriz(quadranteF, quadranteH, novoTamanho, valorCor), novoTamanho, valorCor);
    // P2 = (A+B).H
    P2 = algoritmoStrassen(somaMatriz(quadranteA, quadranteB, novoTamanho, valorCor), quadranteH, novoTamanho, valorCor);
    // P3 = (C+D).E
    P3 = algoritmoStrassen(somaMatriz(quadranteC, quadranteD, novoTamanho, valorCor), quadranteE, novoTamanho, valorCor);
    // P4 = D.(G-E)
    P4 = algoritmoStrassen(quadranteD, subtraiMatriz(quadranteG, quadranteE, novoTamanho, valorCor), novoTamanho, valorCor);
    // P5 = (A+D).(E+H)
    P5 = algoritmoStrassen(somaMatriz(quadranteA, quadranteD, novoTamanho, valorCor), somaMatriz(quadranteE, quadranteH, novoTamanho, valorCor), novoTamanho, valorCor);
    //P6 = (B-D).(G+H)
    P6 = algoritmoStrassen(subtraiMatriz(quadranteB, quadranteD, novoTamanho, valorCor), somaMatriz(quadranteG, quadranteH, novoTamanho, valorCor), novoTamanho, valorCor);
    //P7 = (A-C).(E+F)
    P7 = algoritmoStrassen(subtraiMatriz(quadranteA, quadranteC, novoTamanho, valorCor), somaMatriz(quadranteE, quadranteF, novoTamanho, valorCor), novoTamanho, valorCor);

    // Combinando os produtos em uma nova matriz
    for (int i = 0; i < novoTamanho; i++) {
        for (int j = 0; j < novoTamanho; j++) {
            for (int k = 0; k < valorCor; k++) {
                // Primeiro quadrante = P5 + P4 - P2 + P6
                matrizRes[i][j].cor[k] = P5[i][j].cor[k] + P4[i][j].cor[k] - P2[i][j].cor[k] + P6[i][j].cor[k];
                // Segundo quadrante = P1 + P2
                matrizRes[i][j + novoTamanho].cor[k] = P1[i][j].cor[k] + P2[i][j].cor[k];
                // Terceiro quadrante = P3 + P4
                matrizRes[i + novoTamanho][j].cor[k] = P3[i][j].cor[k] + P4[i][j].cor[k];
                // Quarto quadrante = P1 + P5 − P3 − P7
                matrizRes[i + novoTamanho][j + novoTamanho].cor[k] = P5[i][j].cor[k] + P1[i][j].cor[k] - P3[i][j].cor[k] - P7[i][j].cor[k];
            }
        }
    }

    liberaMatriz(quadranteA, novoTamanho);
    liberaMatriz(quadranteB, novoTamanho);
    liberaMatriz(quadranteC, novoTamanho);
    liberaMatriz(quadranteD, novoTamanho);
    liberaMatriz(quadranteE, novoTamanho);
    liberaMatriz(quadranteF, novoTamanho);
    liberaMatriz(quadranteG, novoTamanho);
    liberaMatriz(quadranteH, novoTamanho);

    liberaMatriz(P1, novoTamanho);
    liberaMatriz(P2, novoTamanho);
    liberaMatriz(P3, novoTamanho);
    liberaMatriz(P4, novoTamanho);
    liberaMatriz(P5, novoTamanho);
    liberaMatriz(P6, novoTamanho);
    liberaMatriz(P7, novoTamanho);

    return matrizRes;
}