---
# System prepended metadata

title: CP2 MID 參考答案
tags: [MID]

---

# CP2 MID 參考答案


## 1. Matrix Multiplication
Credit: 41047012S 簡碩辰 (有做些微修改)
:::spoiler mid01.c
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

int matrix_multiply(int32_t **result, int32_t **matrix, int32_t **tmp, int32_t result_row, int32_t result_col, int32_t matrix_row, int32_t matrix_col) {
    if (result_col != matrix_row) {
        printf("Multiplication Fails\n");
        return -1;
    }
    
    for(int i = 0; i < result_row; i++) {
        for(int j = 0; j < matrix_col; j++) {
            tmp[i][j] = 0;
            for (int k = 0; k < result_col; k++) {
                tmp[i][j] += result[i][k] * matrix[k][j];
            }
        }
    }

    return 0;
}


int main() {
    int32_t count = 1;
    int32_t **result = NULL;
    int32_t result_row, result_col;
    while (1) {
        printf("%d matrix: ", count);

        char *input = calloc(sizeof(char), 1000);
        fgets(input, 1000, stdin);
        if (input[strlen(input) - 1] == '\n')
            input[strlen(input) - 1] = '\0';

        if (strcmp(input, "end") == 0) {
            free(input);
            printf("Result: [");
            for(int i = 0;i < result_row;i++) {
                printf("[");
                for(int j = 0;j < result_col;j++) {
                    printf("%d",result[i][j]);
                    if(j != result_col-1)
                        printf(",");
                }
                printf("]");
                if(i != result_row-1)
                    printf(",");
            }
            printf("]\n");
            break;
        }

        int32_t cnt = 0;
        int32_t len = strlen(input);
        int32_t right_bracket_count = 0,left_bracket_count = 0, comma = 0;
        for (int i = 0; i < len; i++) {
            if (input[i] == ']') {
                right_bracket_count++;
                cnt++;
            }
            else if (input[i] == '[') {
                left_bracket_count++;
                cnt++;
            }
            else if (input[i] == ',') {
                comma++;
                cnt++;
            }
        }
        if(right_bracket_count != left_bracket_count || cnt == len) {
            printf("Invalid Input\n");
            return 0;
        }

        int32_t row = right_bracket_count - 1;
        int32_t col = (comma - (row - 1)) / row + 1;

        int32_t **matrix = calloc(sizeof(int32_t *), row);
        for (int i = 0; i < row; i++)
            matrix[i] = calloc(sizeof(int32_t), col);
        int32_t i = 0, j = 0;
        char *token = strtok(input, ",[]");
        while (token != NULL) {
            if (i < row && j < col) {
                matrix[i][j] = atoi(token);
                j++;
                if (j >= col) {
                    j = 0;
                    i++;
                }
            }
            token = strtok(NULL, ",[]");
        }

        if (count > 1) {
            int32_t tmp_row = result_row, tmp_col = col;
            int32_t **tmp = calloc(sizeof(int32_t*),tmp_row);
            for(int i = 0;i < tmp_row;i++)
                tmp[i] = calloc(sizeof(int32_t),tmp_col);

            if(matrix_multiply(result, matrix, tmp, result_row, result_col, row, col) == -1)
                return 0;

            for (int i = 0; i < result_row; i++)
                free(result[i]);
            free(result);

            result = tmp;
            result_row = tmp_row;
            result_col = tmp_col;
        } else {
            result_row = row;
            result_col = col;
            result = calloc(sizeof(int32_t *), result_row);
            for (int i = 0; i < result_row; i++)
                result[i] = calloc(sizeof(int32_t), result_col);

            for (int i = 0; i < result_row; i++) {
                for (int j = 0; j < result_col; j++) {
                    result[i][j] = matrix[i][j];
                }
            }
        }

        for (int i = 0; i < row; i++)
            free(matrix[i]);
        free(matrix);

        free(input);
        count++;
    }

    if (result != NULL) {
        for (int i = 0; i < result_row; i++)
            free(result[i]);
        free(result);
    }

    return 0;
}

```
:::

## 2. Text Compression

:::spoiler

```clike=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <stdbool.h>
#include <stdint.h>

#define MAX_CODE_LENGTH 20
#define BUFFER_SIZE 1024

typedef struct {
    char symbol;
    char code[MAX_CODE_LENGTH + 1];
} CodebookEntry;

int32_t loadCodebook(const char* filename, CodebookEntry codebook[], int32_t* size);
void encode(const char* inputFilename, const char* outputFilename, CodebookEntry codebook[], int32_t size);

int main() {
    char codebookFile[100], inputFile[100], outputFile[100];
    CodebookEntry codebook[30]; // max 29 entries
    int32_t size = 0;

    printf("Codebook: ");
    scanf("%s", codebookFile);

    if (loadCodebook(codebookFile, codebook, &size) != 0) {
        fprintf(stderr, "Failed to load codebook.\n");
        return 1;
    }
    printf("Input File: ");
    scanf("%s", inputFile);
    printf("Output File: ");
    scanf("%s", outputFile);
    encode(inputFile, outputFile, codebook, size);

    return 0;
}

int32_t loadCodebook(const char* filename, CodebookEntry codebook[], int32_t* size) {
    FILE* file = fopen(filename, "r");
    if (file == NULL) {
        fprintf(stderr, "Failed to open file \"%s\".\n", filename);
        return 1;
    }

    char buffer[BUFFER_SIZE];
    char *line = NULL;
    size_t len = 0;
    ssize_t read;

    while ((read = getline(&line, &len, file)) != -1) {
        char symbol[10], code[MAX_CODE_LENGTH + 1];
        sscanf(line, "%s %s", symbol, code);
        symbol[strlen(symbol) - 1] = '\0'; // remove ':'

        // comma, space, period, a-z
        if (strncmp(symbol, "space", 5) == 0) { 
            codebook[*size].symbol = ' ';
        } else if (strncmp(symbol, "comma", 5) == 0) {
            codebook[*size].symbol = ',';
        } else if (strncmp(symbol, "period", 6) == 0) {
            codebook[*size].symbol = '.';
        } else if (symbol[0] >= 'a' && symbol[0] <= 'z'&& strlen(symbol) == 1){
            codebook[*size].symbol = symbol[0];
        } else {
            fprintf(stderr, "Invalid symbol \"%s\".\n", symbol);
            return 1;
        }
        strcpy(codebook[*size].code, code);
        (*size)++;
    }

    fclose(file);
    return 0;
}

void encode(const char* inputFilename, const char* outputFilename, CodebookEntry codebook[], int32_t size) {
    
    FILE* inputFile = fopen(inputFilename, "r");
    char outputBuffer[BUFFER_SIZE];
    outputBuffer[0] = '\0';
    char buffer[BUFFER_SIZE];
    while (fgets(buffer, BUFFER_SIZE, inputFile) != NULL) {
        for (int32_t i = 0; buffer[i] != '\0'; i++) {
            bool matched = false;
            for (int32_t j = 0; j < size; j++) {
                if (buffer[i] == codebook[j].symbol) {
                    strncat(outputBuffer, codebook[j].code, BUFFER_SIZE - strlen(outputBuffer) - 1);
                    matched = true;
                    break;
                } 
            }
            if (!matched) {
                fprintf(stderr, "Invalid symbol \"%c\".\n", buffer[i]);
                return;
            }
        }
    }
    fclose(inputFile);

    int32_t padding = 8 - (strlen(outputBuffer) % 8);
    size_t currentLength = strlen(outputBuffer);
    outputBuffer[currentLength] = '1';
    for (int32_t i = 1; i <= padding; i++) {
        outputBuffer[currentLength + i] = '0';
    }
    outputBuffer[currentLength + padding] = '\0';

    FILE* outputFile = fopen(outputFilename, "wb");
    for (int32_t i = 0; i < strlen(outputBuffer); i += 8) {
        char byte = 0;
        for (int32_t j = 0; j < 8; j++) {
            byte = byte << 1;
            byte += outputBuffer[i + j] - '0';
        }
        fwrite(&byte, 1, 1, outputFile);
    }
    fclose(outputFile);
}
```

:::

## 3. Face/Off
Credit by: 41247039S 韓Ｏ劭

:::spoiler mid03.c
```c=
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#include "mybmp.h"
#include "myfile.h"

int32_t processFile(FILE *cov, FILE *new, FILE *out, int32_t x, int32_t y, int32_t w, int32_t h);

int main() {
    FILE *covFile = NULL;
    FILE *newFile = NULL;
    FILE *outFile = NULL;

    char covName[F_SIZE] = {0};
    char newName[F_SIZE] = {0};
    char outName[F_SIZE] = {0};

    printf("cover: ");

    if (inputFileName(covName) != 0) {
        return 1;
    }

    if (openFile(&covFile, covName, "rb") != 0) {
        return 1;
    }

    int32_t x, y, w, h;

    printf("x (in pixel): ");
    scanf("%d", &x);

    printf("y (in pixel): ");
    scanf("%d", &y);

    printf("w (in pixel): ");
    scanf("%d", &w);

    printf("h (in pixel): ");
    scanf("%d", &h);

    // Clear input buffer
    while (getchar() != '\n');

    printf("new: ");

    if (inputFileName(newName) != 0) {
        return 1;
    }

    if (openFile(&newFile, newName, "rb") != 0) {
        closeFile(covFile);
        return 1;
    }

    printf("Output file: ");

    if (inputFileName(outName) != 0) {
        closeFile(covFile);
        closeFile(newFile);
        return 1;
    }

    if (strcmp(covName, outName) == 0) {
        printf("Input file name and output file name cannot be the same.\n");
        closeFile(covFile);
        closeFile(newFile);
        return 1;
    }

    if (openFile(&outFile, outName, "wb") != 0) {
        closeFile(covFile);
        closeFile(newFile);
        return 1;
    }

    if (processFile(covFile, newFile, outFile, x, y, w, h) != 0) {
        closeFile(covFile);
        closeFile(newFile);
        closeFile(outFile);
        return 1;
    }

    closeFile(covFile);
    closeFile(outFile);

    return 0;
}

int32_t processFile(FILE *cov, FILE *new, FILE *out, int32_t x, int32_t y, int32_t w, int32_t h) {
    BMP covBMP = {NULL, NULL};
    BMP newBMP = {NULL, NULL};

    if (initBMP(&covBMP, cov) != 0) {
        return 1;
    }

    if (initBMP(&newBMP, new) != 0) {
        freeBMP(&covBMP);
        return 1;
    }

    // TODO: Process BMP here

    int32_t covWidth  = covBMP.header->width;
    int32_t covHeight = covBMP.header->height;

    if (covHeight < 0) {
        covHeight = -covHeight;
    }

    int32_t xPos = x;
    int32_t yPos = covHeight - y - h;

    // if (xPos < 0 || yPos < 0) {
    //     printf("Invalid position\n");
    //     freeBMP(&covBMP);
    //     freeBMP(&newBMP);
    //     return 1;
    // }

    for (int32_t i = 0; i < h; i++) {
        for (int32_t j = 0; j < w; j++) {
            if (xPos + j < 0 || yPos + i < 0 || xPos + j >= covWidth || yPos + i >= covHeight) {
                continue;
            }

            // scale newBMP to w times h
            int32_t newX = (int32_t) (j * (newBMP.header->width - 1) / (w - 1));
            int32_t newY = (int32_t) (i * (newBMP.header->height - 1) / (h - 1));

            covBMP.pixels[yPos + i][xPos + j].r = newBMP.pixels[newY][newX].r;
            covBMP.pixels[yPos + i][xPos + j].g = newBMP.pixels[newY][newX].g;
            covBMP.pixels[yPos + i][xPos + j].b = newBMP.pixels[newY][newX].b;
        }
    }

    if (writeBMP(&covBMP, out) != 0) {
        freeBMP(&covBMP);
        return 1;
    }

    freeBMP(&covBMP);

    return 0;
}

```
:::


:::spoiler mybmp.c
```c=
#include "mybmp.h"

int32_t initBMP(BMP *bmp, FILE *file) {
    if (initBMPHeader(bmp) != 0) {
        return -1;
    }

    if (parseBMPHeader(bmp, file) != 0) {
        freeBMP(bmp);
        return -1;
    }

    if (initBMPPixels(bmp) != 0) {
        freeBMP(bmp);
        return -1;
    }

    if (parseBMPPixels(bmp, file) != 0) {
        freeBMP(bmp);
        return -1;
    }

    return 0;
}

int32_t initBMPHeader(BMP *bmp) {
    bmp->header = (BmpHeader *) calloc(1, sizeof(BmpHeader));

    if (bmp->header == NULL) {
        printf("mybmp: initBMPHeader error");
        return -1;
    }

    return 0;
}

int32_t initBMPPixels(BMP *bmp) {
    int32_t height = bmp->header->height;
    int32_t width  = bmp->header->width;

    if (height < 0) {
        height = -height;
    }

    bmp->pixels = (BmpPixel **) calloc(height, sizeof(BmpPixel *));

    if (bmp->pixels == NULL) {
        printf("mybmp: initBMPPixels height error");
        return -1;
    }

    for (int32_t i = 0; i < height; i++) {
        bmp->pixels[i] = (BmpPixel *) calloc(width, sizeof(BmpPixel));

        if (bmp->pixels[i] == NULL) {
            printf("mybmp: initBMPPixels width error");
            return -1;
        }
    }

    return 0;
}

int32_t parseBMPHeader(BMP *bmp, FILE *file) {
    if (fread(bmp->header, sizeof(BmpHeader), 1, file) != 1) {
        printf("mybmp: parseBMPHeader error");
        return -1;
    }

    // Check if the file is a BMP file

    if (bmp->header->bm[0] != 'B' || bmp->header->bm[1] != 'M') {
        printf("mybmp: parseBMPHeader file error");
        return -1;
    }

    return 0;
}

int32_t parseBMPPixels(BMP *bmp, FILE *file) {
    int32_t width  = bmp->header->width;
    int32_t height = bmp->header->height;

    if (height < 0) {
        height = -height;
    }

    int32_t padding = (width * 3) % 4;

    for (int32_t i = 0; i < height; i++) {
        size_t read = fread(bmp->pixels[i], sizeof(BmpPixel), width, file);

        if (read != (size_t) width) {
            printf("mybmp: parseBMPPixels width error");
            return -1;
        }

        if (padding > 0) {
            fseek(file, padding, SEEK_CUR);
        }
    }

    return 0;
}

int32_t writeBMP(BMP *bmp, FILE *file) {
    // Write BMP header

    if (fwrite(bmp->header, sizeof(BmpHeader), 1, file) != 1) {
        printf("mybmp: writeBMP error");
        return -1;
    }

    // Write BMP pixels

    int32_t width  = bmp->header->width;
    int32_t height = bmp->header->height;

    if (height < 0) {
        height = -height;
    }

    int32_t padding = (4 - (width * 3) % 4) % 4;

    // printf("padding: %d\n", padding);

    for (int32_t i = 0; i < height; i++) {
        if (fwrite(bmp->pixels[i], sizeof(BmpPixel), width, file) != (size_t) width) {
            printf("mybmp: writeBMP error");
            return -1;
        }

        uint8_t zero = 0;

        for (int32_t j = 0; j < padding; j++) {
            if (fwrite(&zero, sizeof(uint8_t), 1, file) != 1) {
                printf("mybmp: writeBMP error");
                return -1;
            }
        }
    }

    return 0;
}

int32_t freeBMP(BMP *bmp) {
    if (bmp == NULL || bmp->header == NULL) {
        return 0;
    }

    int32_t height = bmp->header->height;

    freeBMPHeader(bmp->header);
    freeBMPPixels(bmp->pixels, height);

    return 0;
}

void freeBMPHeader(BmpHeader *header) {
    if (header == NULL) {
        return;
    }

    free(header);
}

void freeBMPPixels(BmpPixel **pixels, int32_t height) {
    if (pixels == NULL) {
        return;
    }

    if (height < 0) {
        height = -height;
    }

    for (int32_t i = 0; i < height; i++) {
        free(pixels[i]);
    }

    free(pixels);
}

```
:::

:::spoiler mybmp.h
```c=
#pragma once

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

typedef struct __attribute__ ((__packed__)) _BmpHeader {
    char	 bm[2];
    uint32_t size;
    uint32_t reserve;
    uint32_t offset;
    uint32_t header_size;
    int32_t  width;
    int32_t  height;
    uint16_t planes;
    uint16_t bpp;
    uint32_t compression;
    uint32_t bitmap_size;
    int32_t  hres;
    int32_t  vres;
    uint32_t used;
    uint32_t important;
} BmpHeader;

typedef struct __attribute__ ((__packed__)) _bmpPixel {
    uint8_t b;
    uint8_t g;
    uint8_t r;
} BmpPixel;

typedef struct _BMP {
    BmpHeader *header;
    BmpPixel **pixels;
} BMP;

/**
 * Initialize BMP from file stream.
 * @param bmp BMP struct
 * @param file file stream
 * @return 0 if success, otherwise non-zero value
 */
int32_t initBMP(BMP *bmp, FILE *file);

/**
 * Initialize BMP header.
 * @param bmp BMP struct
 * @return 0 if success, otherwise non-zero value
 */
int32_t initBMPHeader(BMP *bmp);

/**
 * Initialize BMP pixels.
 * @param bmp BMP struct
 * @return 0 if success, otherwise non-zero value
 */
int32_t initBMPPixels(BMP *bmp);

/**
 * Parse BMP header from file stream.
 * @param bmp BMP struct
 * @param file file stream
 * @return 0 if success, otherwise non-zero value
 */
int32_t parseBMPHeader(BMP *bmp, FILE *file);

/**
 * Parse BMP pixels from file stream.
 * @param bmp BMP struct
 * @param file file stream
 * @return 0 if success, otherwise non-zero value
 */
int32_t parseBMPPixels(BMP *bmp, FILE *file);

/**
 * Write BMP to file stream.
 * @param bmp BMP struct
 * @param file file stream
 * @return 0 if success, otherwise non-zero value
 */
int32_t writeBMP(BMP *bmp, FILE *file);

/**
 * Free BMP.
 * @param bmp BMP struct
 * @return 0 if success, otherwise non-zero value
 */
int32_t freeBMP(BMP *bmp);

/**
 * Free BMP header.
 * @param header BMP header
 */
void freeBMPHeader(BmpHeader *header);

/**
 * Free BMP pixels.
 * @param pixels BMP pixels
 * @param height BMP height
 */
void freeBMPPixels(BmpPixel **pixels, int32_t height);

```
:::

:::spoiler myfile.c
```c=
#include "myfile.h"

int32_t inputFileName(char *file) {
    if (fgets(file, F_SIZE, stdin) == NULL) {
        if (fgetc(stdin) == EOF) {
            printf("myfile: EOF detected\n");
        } else {
            perror("myfile: input error");
        }

        return -1;
    }

    if (file[strlen(file) - 1] == '\n') {
        file[strlen(file) - 1] = '\0';
    }

    return 0;
}

int32_t openFile(FILE **file, char *fileName, char *mode) {
    *file = fopen(fileName, mode);

    if (*file == NULL) {
        char err[F_SIZE] = {0};
        snprintf(err, F_SIZE, "myfile: '%s' error", fileName);
        perror(err);

        return -1;
    }

    return 0;
}

void closeFile(FILE *file) {
    if (file == NULL) {
        return;
    }

    fclose(file);
}

```
:::

:::spoiler myfile.h
```c=
#pragma once

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

#define F_SIZE 4096

/**
 * Input a file name.
 * @param fileName the file name to be set.
 * @return 0 if the input is successful, -1 otherwise.
 */
int32_t inputFileName(char *fileName);

/**
 * Open a file.
 * @param file the file stream pointer.
 * @param fileName the file name.
 * @param mode the open mode.
 * @return 0 if the file is opened successfully, -1 otherwise.
 */
int32_t openFile(FILE **file, char *fileName, char *mode);

/**
 * Close a file.
 * @param file the file stream pointer.
 */
void closeFile(FILE *file);

```
:::

## 4. Colorful Fantastic Render System []


Credit by: 40921135L 黃嘉

:::spoiler mid04.c
```c=
#include <stdio.h>
#include <stdlib.h>

#define WIDTH 256
#define HEIGHT 256

#pragma pack(push, 1)
typedef struct {
    unsigned short type;
    unsigned int size;
    unsigned short reserved1;
    unsigned short reserved2;
    unsigned int offset;
    unsigned int header_size;
    int32_t width;
    int32_t height;
    unsigned short planes;
    unsigned short bpp;
    unsigned int compression;
    unsigned int bitmap_size;
    int32_t hres;
    int32_t vres;
    unsigned int used;
    unsigned int important;
} BMPHeader;
#pragma pack(pop)

typedef struct {
    unsigned char r,g,b;
} RGB;

typedef struct {
    BMPHeader header;
    RGB *pixels;
} BMPImage;

RGB changeColor(int colorindex)
{
    RGB color;
    switch (colorindex)
    {
        case 0:
            color.r = 0x00;
            color.g = 0x00;
            color.b = 0x00;
            break;
        case 1:
            color.b = 0x33;
            color.g = 0x66;
            color.r = 0xff;
            break;
        case 2:
            color.b = 0x00;
            color.g = 0xcc;
            color.r = 0x00;
            break;
        case 3:
            color.b = 0x00;
            color.g = 0xcc;
            color.r = 0xcc;
            break;
        case 4:
            color.b = 0xcc;
            color.g = 0x00;
            color.r = 0x00;
            break;
        case 5:
            color.b = 0xcc;
            color.g = 0x00;
            color.r = 0xcc;
            break;
        case 6:
            color.b = 0xcc;
            color.g = 0xcc;
            color.r = 0x00;
            break;
        case 7:
            color.b = 0xff;
            color.g = 0xff;
            color.r = 0xff;
            break;
    }
    return color;
}

int32_t y=128;
int32_t x = 127;
int32_t dy[8] = {1,1,0,-1,-1,-1,0,1};
int32_t dx[8] = {0,1,1,1,0,-1,-1,-1};
int32_t d_index =0;
int32_t color_index = 7;

void route(BMPImage *bmp,const char* commands,int start,int level)
{
    for(int i=start;commands[i]!='\0';i++)
    {
        if(commands[i]=='F')
        {
            // printf("F");
            bmp->pixels[y*WIDTH+x] = changeColor(color_index);
            y+=dy[d_index];
            x+=dx[d_index];
        }
        else if(commands[i]=='R')
        {
            // printf("R");
            d_index++;
            d_index%=8;
        }
        else if(commands[i]=='C')
        {
            // printf("C");
            color_index++;
            color_index%=8;
        }
        else if(commands[i]=='[')
        {
            route(bmp,commands,i+1,1);
            level++;
        }
        else if(commands[i]==']')
        {
            level--;
            if(level==0)
            {
                break;
            }
        }
    }
}

int main() 
{
    char filename[100];
    int32_t r;
    int32_t g;
    int32_t b;
    char commands[300];

    printf("Enter the output filename: ");
    scanf("%99s", filename); 
    getchar();
    printf("Enter the background color (R,G,B): ");
    scanf("(%d,%d,%d)", &r, &g, &b);
    printf("Type code here: ");
    scanf("%s",commands);
    
    BMPImage bmp;
    bmp.header.type = 0x4D42;
    bmp.header.size = 54 + 256*256*3;
    bmp.header.reserved1=0;
    bmp.header.reserved2=0;
    bmp.header.offset = 54;
    bmp.header.header_size = 40; 
    bmp.header.width = 256;
    bmp.header.height = 256;
    bmp.header.planes = 1;
    bmp.header.bpp = 24;
    bmp.header.compression = 0;
    bmp.header.bitmap_size = 256*256*3;
    bmp.header.hres = 0;
    bmp.header.vres = 0;
    bmp.header.used = 0;
    bmp.header.important = 0;
    bmp.pixels = (RGB*)malloc(bmp.header.bitmap_size);

    for(int i = 0; i<(int)(bmp.header.bitmap_size)/3; i++)
    {
        bmp.pixels[i].b = r;
        bmp.pixels[i].g = g;
        bmp.pixels[i].r = b;
    }

    route(&bmp,commands,0,0);
    FILE *file = fopen(filename,"wb");
    fwrite(&bmp.header,sizeof(BMPHeader),1,file);
    fwrite(bmp.pixels,sizeof(RGB),bmp.header.bitmap_size/3,file);

    fclose(file);
    return 0;
}
```
:::