I am attempting to create a polynomial multiplication program in C, where I have implemented a function named pmult for the multiplication of two polynomials. The program works well until the point where polynomials need to be added for the same exponent values. At this stage, I encounter a segmentation fault with the error message:
malloc(): corrupted top size
What should I do?
Example i used:
p1:
No. of elements=5
coeff expo
2 6
5 3
3 2
2 1
3 0
p2:
No. of elements=5
coeff expo
3 7
2 6
5 4
3 2
7 0
Here is the source code:
#include <stdio.h>
#include <stdlib.h>
typedef struct poly {
int coeff;
int expo;
} poly;
poly *pmult(poly *p1, poly *p2, int term1, int term2, int term, int *ptr);
poly *create(int term);
void display(poly *p, int term);
poly *create(int term)
{
poly *p = malloc(term * sizeof(poly));
for (int i = 0; i < term; i++)
{
printf("Enter the coefficient and the exponent of the polynomial:");
scanf("%d%d", &p[i].coeff, &p[i].expo);
}
return p;
}
poly *pmult(poly *p1, poly *p2, int term1, int term2, int term, int *ptr)
{
poly *p3 = malloc(term * sizeof(poly));
int k = 0;
for (int i = 0; i < term1; i++) //Multiplies every poly1's term with every poly2's term and stores them in poly3
{
for (int j = 0; j < term2; j++)
{
p3[k].coeff = p1[i].coeff * p2[j].coeff;
p3[k++].expo = p1[i].expo + p2[j].expo;
}
}
printf("Displaying poly3:\n");
display(p3, k);
int max = p3[0].expo;
for (int i = 1; i < k; i++)
{
if (p3[i].expo > max)
{
max = p3[i].expo;
}
}
printf("\nMAXXXXX..........:%d\n", max);
int h = 0;
poly *p4 = malloc(k * sizeof(poly));
for (int i = max; i >= 0; i--) //if we have a polynomial result as 3X5+4X3+6X3+7X3+3X3+0X2 so we need to format it as 3X5+20X3+0X2
{
int sum = 0;
for (int j = 0; j < k; j++)
{
if (i == p3[j].expo)
{
sum += p3[j].coeff;
}
}
if (sum > 0)
{
p4[h].expo = i;
p4[h++].coeff = sum;
}
}
free(p3);
*ptr = h;
return p4;
}
void display(poly *p, int term)
{
printf("Printing a polynomial......\n");
for (int i = 0; i < term; i++)
{
printf("%dX%d + ", p[i].coeff, p[i].expo);
}
printf("\n");
}
int main()
{
int termp1, termp2;
printf("Enter the no of terms in polynomial one:");
scanf("%d", &termp1);
poly *poly1 = create(termp1);
display(poly1, termp1);
printf("Enter the no of terms in polynomial one:");
scanf("%d", &termp2);
poly *poly2 = create(termp2);
display(poly2, termp2);
int term = termp1 + termp2;
int ptr = 0;
poly *poly3 = pmult(poly1, poly2, termp1, termp2, term, &ptr);
display(poly3, ptr);
return 0;
}
Your method to compute the polynomial product requires a temporary storage of termp1 * termp2 terms instead of the expected maximum of termp1 + termp2. There is buffer overflow when storing some of the computed terms, invoking undefined behavior, corrupting the memory allocation data, as reported by the C library.
Here is a modified version for you to study:
#include <stdio.h>
#include <stdlib.h>
typedef struct poly {
int coeff;
int expo;
} poly;
poly *poly_read(const char *name, int *pterms);
poly *poly_normalize(poly *p, int *pterms);
void poly_display(const char *name, const poly *p, int term);
poly *poly_multiply(const poly *p1, const poly *p2, int term1, int term2, int *pterms);
static int flush_input(void) {
int c;
while ((c = getchar()) != EOF && c != '\n')
continue;
return c;
}
poly *poly_read(const char *name, int *pterms)
{
printf("Enter the no of terms in polynomial %s: ", name);
if (scanf("%d", pterms) != 1 || *pterms <= 0) {
printf("invalid or missing input\n");
return NULL;
}
poly *p = malloc(*pterms * sizeof(poly));
if (p == NULL) {
printf("allocation error\n");
return NULL;
}
for (int i = 0; i < *pterms; i++) {
printf("Enter the coefficient and the exponent of the term: ");
while (scanf("%d%d", &p[i].coeff, &p[i].expo) != 2) {
fprintf(stderr, "input error\n");
if (flush_input() == EOF) {
free(p);
return NULL;
}
}
}
return poly_normalize(p, pterms);
}
int compare_terms(const void *aa, const void *bb)
{
const poly *a = aa;
const poly *b = bb;
return (a->expo < b->expo) - (a->expo > b->expo);
}
poly *poly_normalize(poly *p, int *pterms)
{
int terms = *pterms;
int i, k;
if (terms <= 0 || p == NULL) {
// ensure at least one term
free(p);
p = malloc(sizeof(*p));
if (p != NULL) {
*pterms = 1;
p[0].coeff = 0;
p[0].expo = 0;
}
return p;
}
// Sort the terms by decreasing powers
qsort(p, terms, sizeof(*p), compare_terms);
// Normalize terms
for (k = 0, i = 1; i < terms; i++) {
if (p[k].expo == p[i].expo) {
p[k].coeff += p[i].coeff;
} else {
if (p[k].coeff)
k++;
p[k] = p[i];
}
}
// handle the last term: ensure at least one term
if (k == 0 || p[k].coeff) {
k++;
}
*pterms = k;
// try and reallocate the normalized polynonial
poly *p1 = realloc(p, k * sizeof(poly));
if (p1)
return p1;
else
return p;
}
poly *poly_multiply(const poly *p1, const poly *p2, int term1, int term2, int *pterms)
{
int term3 = term1 * term2;
poly *p3 = malloc(term3 * sizeof(poly));
if (p3 == NULL) {
printf("allocation error\n");
*pterms = 0;
return NULL;
}
*pterms = term3;
int i, j, k = 0;
//Multiply every poly1's term with every poly2's term and stores them in poly3
for (i = 0; i < term1; i++) {
for (j = 0; j < term2; j++, k++) {
p3[k].coeff = p1[i].coeff * p2[j].coeff;
p3[k].expo = p1[i].expo + p2[j].expo;
}
}
poly_display("temp", p3, term3);
return poly_normalize(p3, pterms);
}
int poly_display_term(const poly *p, int i)
{
int coeff = p[i].coeff;
int expo = p[i].expo;
int len = 0;
if (coeff < 0) {
len += printf("-");
coeff = -coeff;
} else
if (coeff > 0) {
if (i > 0) {
len += printf("+");
}
} else {
return 0;
}
if (coeff != 1 || expo == 0) {
len += printf("%d", coeff);
}
if (expo > 0) {
printf("X");
if (expo > 1)
printf("%d", expo);
}
return len;
}
void poly_display(const char *name, const poly *p, int term)
{
int len = 0;
if (name) {
printf("%s: ", name);
}
for (int i = 0; i < term; i++) {
len += poly_display_term(p, i);
}
if (len == 0) {
printf("0");
}
printf("\n");
}
int main(void)
{
int termp1, termp2, termp3;
poly *poly1 = poly_read("poly1", &termp1);
if (poly1 == NULL)
return 1;
poly_display("poly1", poly1, termp1);
poly *poly2 = poly_read("poly2", &termp2);
if (poly2 == NULL)
return 1;
poly_display("poly2", poly2, termp2);
poly *poly3 = poly_multiply(poly1, poly2, termp1, termp2, &termp3);
if (poly3) {
poly_display("poly3", poly3, termp3);
}
free(poly1);
free(poly2);
free(poly3);
return 0;
}
Here is a more user-friendly polynomial parser:
/* realloc block or free and return NULL */
void *realloc_or_free(void *p, size_t size) {
void *new_p = realloc(p, size);
if (new_p == NULL)
free(p);
return new_p;
}
poly *poly_read(const char *name, int *pterms)
{
#if 0
printf("Enter the no of terms in polynomial %s: ", name);
if (scanf("%d", pterms) != 1 || *pterms <= 0) {
printf("invalid or missing input\n");
return NULL;
}
poly *p = malloc(*pterms * sizeof(poly));
if (p == NULL) {
printf("allocation error\n");
return NULL;
}
for (int i = 0; i < *pterms; i++) {
printf("Enter the coefficient and the exponent of the term: ");
while (scanf("%d%d", &p[i].coeff, &p[i].expo) != 2) {
fprintf(stderr, "input error\n");
if (flush_input() == EOF) {
free(p);
return NULL;
}
}
}
return poly_normalize(p, pterms);
#else
char line[200];
printf("Enter polynomial %s: ", name);
if (!fgets(line, sizeof line, stdin)) {
fprintf(stderr, "input error\n");
return NULL;
}
poly *p1 = NULL;
int terms = 0;
unsigned char c;
char *p = line;
int sign = 1;
while ((c = *p++) != '\0') {
if (isspace(c))
continue;
if (c == '-') {
sign = -sign;
continue;
}
if (c == '+')
continue;
p1 = realloc_or_free(p1, (terms + 1) * sizeof(*p1));
if (!p1) {
printf("allocation error\n");
return NULL;
}
p1[terms].coeff = 1;
if (isdigit(c)) {
p1[terms].coeff = strtol(p - 1, &p, 10);
c = ' ';
if (*p == 'X' || *p == 'x')
c = *p++;
}
p1[terms].coeff *= sign;
p1[terms].expo = 0;
if (c == 'X' || c == 'x') {
p1[terms].expo = 1;
if (isdigit((unsigned char)*p)) {
p1[terms].expo = strtol(p, &p, 10);
}
} else
if (!isspace(c)) {
printf("syntax error\n");
printf("%s%*s\n", line, (int)(p - line - 1), "^");
free(p1);
return NULL;
}
terms++;
sign = 1;
}
*pterms = terms;
return poly_normalize(p1, pterms);
#endif
}
Sample output:
Enter polynomial poly1: x3-1
poly1: X3-1
Enter polynomial poly2: x4-1
poly2: X4-1
temp: X7-X3-X4+1
poly3: X7-X4-X3+1