The purpose of my program is to decrypt text using a key.Obviously it will take in that string and key. It will sort this text in a matrix. So a text like hello will be read down the column. They key determines the amount of columns there are. The key is alphabetically sorted and the columns are rearranged based on that order. Here is an example of the process.
My problem is that when I enter a key of more than 5 characters long the matrix is messed up and it doesn't work. My code is down below. So it works fine with the example above. But if I use the key as "hacker" and the string as "ehleoehtlr" I get
Row 0: elohl_
Row 1: heetr-
Sorted key: acehkr (length: 6)
Row 0: hloel_
Row 1: teehr-
The expected output is:
Row 0: elohl_
Row 1: heetr-
Sorted key: acehkr (length: 6)
Row 0: hello_
Row 1: there-
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
// use bubble sort to sort letters in a key
void sort_letters(char *phrase) {
int i,j;
int n = strlen(phrase);
//printf("The string to sort is: %s\n", phrase);
for ( i = 0; i < n-1; i ) {
for ( j = i 1; j < n; j ) {
if (phrase[i] > phrase[j]) {
char temp = phrase[i];
phrase[i] = phrase[j];
phrase[j] = temp;
}
}
}
//printf("The sorted string is: %s\n", phrase);
}
// allocate a matrix for string and fill it
char** gridStr(char *line, char *key)
{
int n = strlen(line);
int columns = strlen(key);
int rows = (n columns - 1) / columns;
int j;
char **matrix = malloc(rows * sizeof(char *));
for ( j = 0; j < rows; j ) {
matrix[j] = malloc(columns * sizeof(char));
}
int i = 0;
int k,l;
for ( l = 0; l < columns; l ) {
for ( k = 0; k < rows; k ) {
if (i<n) {
matrix[k][l] = line[i ];
} else {
matrix[k][l] = '-'; // fill letter
}
//putchar(matrix[k][l]);
}
//putchar('\n');
}
return matrix;
}
// swap columns i and j of the given matrix, zero-based indices
void swap_matrix_columns(char **matrix, int rows, int columns, int i, int j) {
int k;
for ( k = 0; k < rows; k ) {
char tmp = matrix[k][i];
matrix[k][i] = matrix[k][j];
matrix[k][j] = tmp;
}
}
// print matrix to stdout
void print_matrix1(char **matrix, int rows, int columns) {
int i,j;
for (i = 0; i < rows; i ) {
printf("Row -: ", i);
for (j = 0; j < columns; j ) {
if (matrix[i][j] == ' ') {
putchar('_');
} else {
putchar(matrix[i][j]);
}
}
putchar('\n');
}
for(i=0; i<rows; i ) {
for(j=0;j<columns;j ) {
printf("%c", matrix[i][j]);
}
}
}
// sort key and transpose matrox columns according new order
void decrypt(char **matrix, int rows, int columns, char *key) {
char sorted_key[strlen(key) 1];
strcpy(sorted_key, key);
sort_letters(sorted_key);
printf("Sorted key: %s (length: %2zu)\n", sorted_key, strlen(sorted_key));
bool is_used[columns];
int i;
for ( i = 0; i < columns; i ) is_used[i]= false;
for ( i = 0; i < columns; i ) {
if (!is_used[i]) {
// find new position, must exist
int j;
for (j = 0; j < columns; j ) {
if (key[i] == sorted_key[j] && !is_used[j]) {
break;
}
}
swap_matrix_columns(matrix, rows, columns, i, j);
is_used[i] = true;
//is_used[j] = true;
}
}
}
int main(void) {
char key[50];
char line[256];
printf("Enter your string: ");
if (fgets(line, sizeof line, stdin) == NULL) {
fprintf(stderr, "No line read\n");
exit(EXIT_FAILURE);
}
printf("Enter your key: ");
if (fgets(key, sizeof key, stdin) == NULL) {
fprintf(stderr, "No line read\n");
exit(EXIT_FAILURE);
}
int len = strlen(line);
if (len && line[len - 1] == '\n') {
line[--len] = '\0';
}
int len1 = strlen(key);
if (len1 && key[len1 - 1] == '\n') {
key[--len1]= '\0';
}
//printf("string: |%s| (length: %2zu)\n", line, strlen(line));
//printf("key: |%s| (length: %2zu)\n", key, strlen(key));
char **matrix = gridStr(line, key);
int columns = len1;
// Use simple trick ( len1 - 1) to determine number of rows with one integer divison
int rows = (len columns - 1) / columns;
//print_matrix1(matrix, rows, columns);
decrypt(matrix, rows, columns, key);
print_matrix1(matrix, rows, columns);
int i;
int row;
for ( row = 0; row < rows; row ) {
free(matrix[row]);
}
free(matrix);
return EXIT_SUCCESS;
}
CodePudding user response：
For your example input, in this section of code passes argument value of j == 6 which will cause fatal run-time error. (See comment):
for ( i = 0; i < columns; i ) {
if (!is_used[i]) {
// find new position, must exist
int j;
for (j = 0; j < columns; j ) {
if (key[i] == sorted_key[j] && !is_used[j]) {
break;
}
}//at this point j == columns (6)
swap_matrix_columns(matrix, rows, columns, i, j);//j == 6
is_used[i] = true;
//is_used[j] = true;
}
}
Causing this section of code to drereference an out of bounds pointer:
void swap_matrix_columns(char **matrix, int rows, int columns, int i, int j) {
int k;
for ( k = 0; k < rows; k ) {
char tmp = matrix[k][i];
matrix[k][i] = matrix[k][j];//fails when k==0 and j==6
matrix[k][j] = tmp;
}
Valid index ranging for matrix is [0-1][0-5]c
Placing swap_matrix_columns(matrix, rows, columns, i, j);within the inner for loop should address this problem:
for (j = 0; j < columns; j ) {
if (key[i] == sorted_key[j] && !is_used[j]) {
break;
}
swap_matrix_columns(matrix, rows, columns, i, j);
}
//swap_matrix_columns(matrix, rows, columns, i, j);//j == 6
is_used[i] = true;
With that change, and using the example input you show in your code, the output looks like this:
Enter your string: ehleoehtlr
Enter your key: hacker
Sorted key: acehkr (length: 6)
Row 0: ll-oeh
Row 1: re-eht
ll-oehre-eht
Because your expectations are not clearly stated, this may or may not be correct.
By the way, at this point in your program:
decrypt(matrix, rows, columns, key);
print_matrix1(matrix, rows, columns);
The contents of memory for matrix looks like this:
CodePudding user response：
This is not a complete answer, but a hint where to look for the error.
When I compile your program with gcc ... -fsanitize=address -fsanitize=undefined, I get an error report:
=================================================================
==2221==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000076 at pc 0x55b8430d5212 bp 0x7ffc94a620e0 sp 0x7ffc94a620d0
READ of size 1 at 0x602000000076 thread T0
#0 0x55b8430d5211 in swap_matrix_columns /home/main.c:62
#1 0x55b8430d5ffe in decrypt /home/main.c:114
#2 0x55b8430d694c in main /home/main.c:161
#3 0x7ff0266b3082 in __libc_start_main ../csu/libc-start.c:308
#4 0x55b8430d444d in _start (/home/a.out 0x544d)
0x602000000076 is located 0 bytes to the right of 6-byte region [0x602000000070,0x602000000076)
allocated by thread T0 here:
#0 0x7ff027bf0808 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cc:144
#1 0x55b8430d4add in gridStr /home/main.c:34
#2 0x55b8430d687a in main /home/main.c:152
#3 0x7ff0266b3082 in __libc_start_main ../csu/libc-start.c:308
Line 62 is matrix[k][i] = matrix[k][j];
Line 34 is matrix[j] = malloc(columns * sizeof(char));
As the error message refers to a READ access, and because of the corresponding malloc, it must be the access to matrix[k][j] and the index j seems to be one more than the allowed maximum.
Without further analysis I guess the problem is related to this code in function decrypt:
for (j = 0; j < columns; j ) {
if (key[i] == sorted_key[j] && !is_used[j]) {
break;
}
}
swap_matrix_columns(matrix, rows, columns, i, j);
If the for loop is terminated by the break, The value of j fulfills the condition j < columns which is a valid column index. Otherwise it will be j == columns which would result in an invalid array acces in swap_matrix_columns because this index j is one more than the last valid column index.
You don't distinguish between the different cases. One way to do this would be to check if j is a valid column before or in swap_matrix_columns.
I didn't analyze your algorithm, so I don't know what it should do when the loop terminates with j >= columns if no matching unused key column was found. (I don't know if simply not calling swap_matrix_columns in this case is correct.
Possible (equivalent) solutions might be
for (j = 0; j < columns; j ) {
if (key[i] == sorted_key[j] && !is_used[j]) {
break;
}
}
if(j < columns) {
swap_matrix_columns(matrix, rows, columns, i, j);
}
or
for (j = 0; j < columns; j ) {
if (key[i] == sorted_key[j] && !is_used[j]) {
swap_matrix_columns(matrix, rows, columns, i, j);
break;
}
}