Hi! all
I have a problem in a C program; it crashes while on 'free()' inside a recursive function, the message being that it cannot find a pointer on the heap.
It computes factorial numbers of biiig length using strings of digits rather than numeric variables. Because I could not find the bug, I modified the program so that I can use a loop instead than recursion if I choose to do so; well the problem disappears, using a loop, and the rest of the code (doing 'N * (N - 1) etc.) remains the same.
In recursive mode there is some kind of overflow, I can see it using 'printf()' but am not able to fix it, and all that the recursive function does is allocating memory to accommodate 'N -1' N - 1 times then copies 'N' to that memory, calls a function to do the actual '- 1' operation, and calls a 'multiplication' function which returns the partial result. Exactly the same thing, using the same functions happens in the 'loopit()' function; the only difference is that in this case I can normally free the allocate memory.
In the 'multiplication' function 'realloc()' is called when needed, ad that seems to be part of the bug, but that (exactly the same) is done in either modes, and when linked to '-ldmalloc' all memory results as freed in 'loop' mode, but "free()' is crashing in 'recurse' mode.
The only way I am able to get it to work in recursive mode is by calculating the total number of digits in the eventual factorial, then
allocating that length + 2 to the 'number' string in 'main()', and passing the size as a pointer to the other functions; that way 'realloc()' needs not be called, but it involves calculating the number o digits before hand.
So probably 'realloc()' is the problem, but it is called extensively in 'loop' mode without problems.
I'm attaching the source, but this version cannot do the job explained above (number of digits in advance), so it crashes in 'recurse' mode on big numbers.
Thank you for having read all this, and some suggestions would be appreciated.
Regards marian57
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#ifdef DMALLOC
#include <dmalloc.h>
#endif
#define MESS "Usage:\n\
<prog> [-h]|[-l <num1> [<num2>]]\n\
Description:\n\
Computes the factorial of 'num1', or multiplies 'num1' by 'num2'.\n\
Options:\n\
-h - Print this\n\
-l - Compute the factorial of 'num1' using a loop, rather than recursion."
int NOREC = 0;
char *loopit(char *nu, int *sz);
char *fact(char *n, int *sz);
char *mulstr(char *st1, char *st2, int *s);
char *subone(char *sb);
char *reverse(char *rv);
/* ************************************************************************ */
int main(int argc, char **argv) {
int l = 0, i, num1 = -1, num2 = -1;
for(i = 1; i < argc; i++) {
if(!strcmp(argv[i], "-h")) {
puts(MESS);
return 0;
}
else if(!strcmp(argv[i], "-l"))
NOREC = 1;
else if(isdigit(*argv[i])) {
if(num1 == -1)
num1 = atoi(argv[i]);
else if(num2 == -1)
num2 = atoi(argv[i]);
else {
puts("\aMaximum 2 numbers.");
puts(MESS);
exit(1);
}
}
else {
puts("\aInvalid argument.");
puts(MESS);
exit(1);
}
}
if(num1 == -1 && num2 == -1)
puts("\a\nWe need a number.");
else if(num1 > -1 && num2 > -1) {
int sz = 16;
char *m1 = malloc(sz), *m2 = malloc(sz);
if(!m1 || !m2) {
perror("Allocation m1/m2");
exit(1);
}
sprintf(m1, "%d", num1);
sprintf(m2, "%d", num2);
m1 = mulstr(m1, m2, &sz);
printf("%d * %d =\n %s\n", num1, num2, m1);
}
else {
int num = num1;
for(;
{
if(!*argv[1]) {
puts("\n<Enter> another number.");
scanf("%d", &num);
if(num < 0)
return 0;
while(getchar() != '\n');
}
system("clear");
int s = 16; /* The size which will grow to the eventual length of n1!. */
char *n1 = malloc(s);
sprintf(n1, "%d", num);
if(NOREC)
n1 = loopit(n1, &s);
else
n1 = fact(n1, &s);
l = strlen(n1);
printf("%d! = %s\nused %d bytes\nis %d digits long.\n", num, n1, s, l);
free(n1);
argv[1] = "";
num = -1;
}
}
return 0;
}
/* Computes N! usinf a loop. */
/* ************************************************************************ */
char *loopit(char *nu, int *sz) {
char *snu = malloc(strlen(nu) + 1);
if(!snu) {
perror("Allocation snu");
exit(1);
}
strcpy(snu, nu);
while(strcmp(snu, "1")) {
*sz = strlen(nu) + 1;
snu = subone(snu);
if(!strcmp(snu, "1"))
break;
nu = mulstr(nu, snu, sz);
}
free(snu);
return nu;
}
/* Recursively computes N! in the form of string f. */
/* ************************************************************************ */
char *fact(char *f, int *s) {
if(!strcmp(f, "1") || !strcmp(f, "0"))
strcpy(f, "1");
else {
char *mone = malloc(strlen(f) + *s + 10);
if(!mone) {
perror("Allocation mone");
exit(1);
}
strcpy(mone, f);
mone = subone(mone);
if(f && *f && mone && *mone) {
if(strcmp(mone, "1"))
f = mulstr(f, fact(mone, s), s);
free(mone);
}
else {
printf("ERROR\a empty string.\n");
getchar();
}
}
return f;
}
/* Multiplies a * b in the form of strings st1 and st2. */
/* ************************************************************************ */
char *mulstr(char *st1, char *st2, int *s) {
char *m1 = st1, *m2 = st2, *p1 = NULL, *p2 = NULL;
char **lines = NULL;
char *swap = NULL;
int i, j, k, l2 = 0, l1 = 0, cr;
if(strlen(st1) < strlen(st2)) {
m1 = st2;
m2 = st1; /* Pointer to the short string */
}
l2 = strlen(m2);
l1 = strlen(m1);
if((lines = (char**)malloc(sizeof(char*) * l2)) == NULL) {
perror("Allocation lines 0");
exit(1);
}
for(i = 0; i < l2; i++) {
if((lines[i] = (char*)malloc(l1 + l2 + 2)) == NULL) {
perror("Allocation 1");
exit(1);
}
}
p2 = m2 + l2 - 1;
i = 0;
cr = 0;
while(p2 >= m2) {
int n2 = *p2 - 48, n5 = 0;
j = 0;
p1 = m1 + l1 - 1;
cr = 0;
while(p1 >= m1) {
int n1 = *p1 - 48, n3 = n1 * n2 + cr, n4 = n3 / 10;
n5 = n3 % 10;
lines[i][j++] = n5 + 48;
cr = n4;
p1--;
}
lines[i][j++] = cr + 48;
lines[i][j] = 0;
for(k = i; k < l2 - 1; k++)
strcat(lines[i], "0");
lines[i] = reverse(lines[i]);
for(k = 0; k < i; k++)
strcat(lines[i], "0");
i++;
p2--;
}
if(*s < l1 + l2 + 2) {
*s = l1 + l2 + 2;
if((st1 = (char*)realloc(st1, *s)) == NULL) {
perror("Allocation st1 re");
exit(1);
}
}
memset(st1, 48, l1 + l2 + 2);
*(st1 + l1 + l2 + 1) = 0;
cr = 0;
for(k = l1 + l2 - 1; k >= 0; k--) {
int dtot = 0, d1, d2;
for(i = 0; i < l2; i++)
dtot += (lines[i][k] - 48);
dtot += cr;
d1 = dtot / 10;
d2 = dtot % 10;
cr = d1;
st1[k + 1] = d2 + 48;
}
st1[0] = cr + 48;
st1[l1 + l2 + 1] = 0;
if((swap = (char*)malloc(*s)) == NULL) {
perror("Allocation swap");
exit(1);
}
strcpy(swap, st1);
while(*swap && *swap == '0')
memmove(swap, swap + 1, strlen(swap));
strcpy(st1, swap);
free(swap);
for(i = 0; i < l2; i++)
free(lines[i]);
free(lines);
return st1;
}
/* Reverses a string of digits. */
/* ************************************************************************ */
char *reverse(char *rv) {
int ln = strlen(rv);
char *p = rv + ln - 1, *tmp = alloca(ln + 1);
int j = 0;
if(!tmp) {
perror("Allocation tmp");
exit(1);
}
while(p >= rv) {
*(tmp + j++) = *p;
p--;
}
*(tmp + j) = 0;
strcpy(rv, tmp);
return rv;
}
/* 'subtracts' 1 from a string of digits. */
/* ************************************************************************ */
char *subone(char *sb) {
int nm = atoi(sb) -1;
sprintf(sb, "%d", nm);
return sb;
}
