Copying memory in C

[danbaron]

I was thinking about seeing how fast I could do arithmetic on big integers using C.

The first problem is, how to store a big integer. It turns out that a char array works good.

The second problem is, that you may not know in advance how big an integer will be.

You don't want to, for instance, reserve 1000 bytes, for an integer that only has 20 digits, and so, needs only 20 bytes.

What you can do is, have one char array (buffer) large enough to contain any permissible integer. An integer goes into the buffer, and its size is determined. Then, a char array of the integer's exact size in bytes is allocated for the integer, and the memory is copied from the buffer, to the integer's char array.

:idea:

---------------------------------------------------

An IDE (and compiler) that I like for C, is Pelles C.
A new version was recently released.

http://www.christian-heffner.de/

Once you have a C program the way you want it, you can make it run fast by compiling it with GCC.
MinGW (Minimalist GNU for Windows) is a Windows version of GCC.

http://www.mingw.org/wiki/Getting_Started

GCC options

http://gcc.gnu.org/onlinedocs/gcc/Option-Summary.html

GCC optimization options

http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#Optimize-Options
(http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#Optimize-Options)

'code ---------------------------------------------------------------------------------------------------

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

//-------------------------------------------------------------------------------------------------------

char* makechararray (unsigned long int nchars)
{
return (char *) malloc (nchars);
}

//-------------------------------------------------------------------------------------------------------

unsigned long int chararraylength (char* chararray)
{
return strlen (chararray);
}

//-------------------------------------------------------------------------------------------------------

void copymemory(char* to, char* from, unsigned long int length)
{
memcpy(to, from, length);
}

//-------------------------------------------------------------------------------------------------------

int main()
{
int maxchars = 10000;
char* numbuffer;
char* num1;
char* num2;
int numbufferlength;
int num1length;
int num2length;

// Make a big buffer to contain a numeric string.
// Make it big enough to hold the largest integer you will accept.
numbuffer = makechararray(maxchars);

numbuffer = "47375635267869584736475678475639785767575768594";
numbufferlength = chararraylength(numbuffer);

// Make the storage for num1 only as big as it needs to be.
num1 = makechararray(numbufferlength);

// Copy the number from numbuffer to num1.
copymemory(num1, numbuffer, numbufferlength);

// Once you have num1, you can find its length, you don't need to use numbufferlength.
num1length = chararraylength(num1);

printf("numbuffer = %s\n", numbuffer);
printf("num1 = %s\n", num1);
printf("bytes allotted for num1 = %u\n", num1length);
printf("\n");

numbuffer = "879573647581637466839127485763902089079688582735127937457285364758837581232354970";
numbufferlength = chararraylength(numbuffer);

// Make the storage for num2 only as big as it needs to be.
num2 = makechararray(numbufferlength);

// Copy the number from numbuffer to num2.
copymemory(num2, numbuffer, numbufferlength);

// Once you have num2, you can find its length, you don't need to use numbufferlength.
num2length = chararraylength(num2);

printf("numbuffer = %s\n", numbuffer);
printf("num2 = %s\n", num2);
printf("bytes allotted for num2 = %u\n", num2length);
printf("\n");

return 0;
}

' output ------------------------------------------------------------------------------------------------

numstring = 47375635267869584736475678475639785767575768594
num1 = 47375635267869584736475678475639785767575768594
bytes allotted for num1 = 47

numstring = 879573647581637466839127485763902089079688582735127937457285364758837581232354970
num2 = 879573647581637466839127485763902089079688582735127937457285364758837581232354970
bytes allotted for num2 = 81

Press any key to continue...

[danbaron]

I had an error in the code above.

It seemed to run OK for me, but, I guess that was just luck.

In the function, "chararraylength", I had the statement, "return strlen(chararray);".

The statement should be, "return strlen(chararray) + 1;".

Without the "1", all kinds of crazy things happen, as I found out when I added the new function, "changechararray".

I was just about ready to give up and blame C, when I found what was wrong.

"changechararray", is used to change the value of a big integer, as shown below.

:idea: :?:



' code --------------------------------------------------------------------------------------------------

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

//-------------------------------------------------------------------------------------------------------

char* makechararray(unsigned long int nchars)
{
return (char *) malloc(nchars);
}

//-------------------------------------------------------------------------------------------------------

unsigned long int chararraylength(char* chararray)
{
return strlen(chararray) + 1;
}

//-------------------------------------------------------------------------------------------------------

void copymemory(char* to, char* from, unsigned long int length)
{
memcpy(to, from, length);
}

//-------------------------------------------------------------------------------------------------------

void changechararray(char* oldarray, char* newarray)
{
unsigned long int newsize = chararraylength(newarray);
realloc(oldarray, newsize);
copymemory(oldarray, newarray, newsize);
}

//-------------------------------------------------------------------------------------------------------

int main()
{
int maxchars = 10000;
char* numbuffer;
char* num1;
int numbufferlength;
int num1length;

// Make a big buffer to contain a numeric string.
// Make it big enough to hold the largest integer you will accept.
numbuffer = makechararray(maxchars);

numbuffer = "79857387940275396856641092";
numbufferlength = chararraylength(numbuffer);

// Make the storage for num1 only as big as it needs to be.
num1 = makechararray(numbufferlength);

// Copy the number from numbuffer to num1.
copymemory(num1, numbuffer, numbufferlength);

// Once you have num1, you can find its length, you don't need to use numbufferlength.
num1length = chararraylength(num1);

printf("numbuffer = %s\n", numbuffer);
printf("num1 = %s\n", num1);
printf("bytes allotted for num1 = %u\n", num1length);
printf("\n");

numbuffer = "636993001002004996875000594937886775818282994887756664100059695999937728819008007";

// Now, change the value of num1.
changechararray(num1, numbuffer);

num1length = chararraylength(num1);

printf("numbuffer = %s\n", numbuffer);
printf("num1 = %s\n", num1);
printf("bytes allotted for num1 = %u\n", num1length);
printf("\n");

numbuffer = "2";

// Now, change it again.
changechararray(num1, numbuffer);

num1length = chararraylength(num1);

printf("numbuffer = %s\n", numbuffer);
printf("num1 = %s\n", num1);
printf("bytes allotted for num1 = %u\n", num1length);
printf("\n");

return 0;
}

' output ------------------------------------------------------------------------------------------------

numbuffer = 79857387940275396856641092
num1 = 79857387940275396856641092
bytes allotted for num1 = 27

numbuffer = 636993001002004996875000594937886775818282994887756664100059695999937728819008007
num1 = 636993001002004996875000594937886775818282994887756664100059695999937728819008007
bytes allotted for num1 = 82

numbuffer = 2
num1 = 2
bytes allotted for num1 = 2

Press any key to continue...

[danbaron]

Now, I found a big problem when using dynamically allocated char arrays in C.

If you use "malloc" to create one in function "main", then, you (or at least I) cannot access its individual chars, except from within main.

If you pass a dynamically allocated char array to another function, then, when you refer to a particular index, either the program crashes, or, it corrupts the array.

The only solution I can think of is to use an int array instead of a char array to represent a big integer. That would mean you would have to copy the string representation of the number into an int array. So, you would therefore incur both the penalties of the extra copying, and, also the extra storage, i.e., you would need both a char buffer and an int buffer, and you would waste 3 out of 4 of each int's bytes.

I guess I'll keep going and see what happens.

---------------------------------------------------------

The way I found out about the limitation, was that my program kept crashing no matter what I tried.

I finally looked in a book, "C Programming FAQs", by, Steve Summit, 1996.

Here is what it says.

-------------------------------

1.32

Question: What is the difference between these initializations?

char a[] = "string literal";
char* p = "string literal";

My program crashes if I try to assign a new value to p[i].

Answer: A string literal - the formal term for a double quoted string in C source - can be used in two slightly different ways:

1.
As the initializer for an array of char, as in the declaration of char a[], it specifies the initial values of the characters in that array and, if necessary, its size.

2.
Anywhere else, it turns into an unnamed, static array of characters, and this unnamed array may be stored in read-only memory, which is why you can't safely modify it. In an expression context, the array is converted at once to a pointer, as usual (see Chapter 6), so the second declaration initializes p to point to the unnamed array's first element.

Some compilers have a switch controlling whether strings are writable (for compiling old code), and some may have options to cause string literals to be formally treated as arrays of const char (for better error catching). See also questions 1.32, 6.1, 6.2, and 6.8.

---------------------------------------------------------

Actually, according to the answer to the question, I don't think there is any guarantee that you can ever successfully alter an individual element of a char array that was initialized as a pointer.

[jack]

Dan, have a look here http://libtom.org/
the software is in the public domain, meaning you can do whatever you want with it, no strings attached.
see the license http://sam.zoy.org/wtfpl/

[danbaron]

I downloaded the fast math library, Johan.

It looks good, I don't know how he did it.

I like the license.

But, I want to try to do something myself.

Otherwise, I won't learn anything.

-------------------------

I am really surprised and angry with C's implementation of strings.

My impression was that they were just plain arrays of type char.

And, that you could use them like arrays of any other type.

But, my experience is that, they are not, and, you cannot.

Look at this code.


' code --------------------------------------------------------------------------------------------------

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

//-------------------------------------------------------------------------------------------------------

char* makechararray(unsigned long int nchars)
{
return (char *) malloc(nchars);
}

//-------------------------------------------------------------------------------------------------------

void crashfunction(char* array)
{
array[0] = 6;
}

//-------------------------------------------------------------------------------------------------------

int main()
{
int maxchars = 10000;
char* badbuffer;

//char goodbuffer[maxchars];
//goodbuffer = "79857387940275396856641092";

char goodbuffer[] = "79857387940275396856641092";

badbuffer = makechararray(maxchars);
badbuffer = "79857387940275396856641092";

crashfunction(goodbuffer);
printf("%u\n", goodbuffer[0]);

crashfunction(badbuffer);
printf("%u\n", badbuffer[0]);

return 0;
}

//-------------------------------------------------------------------------------------------------------
Notice the two lines that are commented out in function "main".

//char goodbuffer[maxchars];
//goodbuffer = "79857387940275396856641092";

They are commented out because, if you try to do it that way, the program will not compile.
You must assign the string when it is declared, like this.

char goodbuffer[] = "79857387940275396856641092";

As the program is shown (with the commented out lines), it will run.

It should print the number 6 twice, in the console window.

But, it only prints 6, once.

When "goodbuffer" is passed to "crashfunction", there is no problem.

But, when "badbuffer" is passed to "crashfunction", the program crashes.

It seems that you cannot access a particular element of a char array that was declared with a pointer.

Wow, to me it is amazing that these, what I would call defects, have not been remedied after so many years of C's existence.

C is always advertised as being so fast, so efficient.

But, what good are speed and efficiency, if one of the fundamental data types, is so flawed?

:cry: :p

[kryton9]

Dan, string handling is terrible if you ask me in C and C++, even with the string class in the STL. Boost has a better one, but still nothing as useful and logical to use and understand as in BASIC.

Here is what I used for strings. This is my Vector3D Class that I wrote and you can see how I managed strings with it.



/*
Vector 3 Class and Functions by Kent Sarikaya (kryton9) November 2008
*/
#ifndef VEC3_H
#define VEC3_H

#include <math.h>
#include <iostream>
#include <string>

// thanks to Petr Schreiber for this fix
#define _CVTBUFSIZE (309+40)

using namespace std;

// All class methods start with an upper case letter
class Vec3
{
public:
Vec3(double X = 0, double Y = 0, double Z = 0)
{
x = X;
y = Y;
z = Z;
}


void Set(double X = 0, double Y = 0, double Z = 0)
{
x = X;
y = Y;
z = Z;
}


void SetX(double X = 0)
{
x = X;
}


void SetY(double Y = 0)
{
y = Y;
}


void SetZ(double Z = 0)
{
z = Z;
}


Vec3 Get(void) const
{
return *this;
}


double GetX(void) const
{
return x;
}


double GetY(void) const
{
return y;
}


double GetZ(void) const
{
return z;
}


Vec3 operator+(const Vec3 &a)
{
return Vec3(a.x + x, a.y + y, a.z + z);
}


Vec3 operator+=(const Vec3 &a)
{
//return Vec3(*this + a);
return (*this = (*this + a));
}


Vec3 operator-(const Vec3 &a)
{
return Vec3(x - a.x, y - a.y, z - a.z);
}


Vec3 operator-=(const Vec3 &a)
{
//return Vec3(*this - a);
return (*this = (*this - a));
}


Vec3 operator*(double scalar)
{
return Vec3(x * scalar, y * scalar, z * scalar);
}


Vec3 operator*=(double scalar)
{
return (*this = (*this * scalar));
}


Vec3 operator/(double scalar)
{
return Vec3(x / scalar, y / scalar, z / scalar);
}



Vec3 operator/=(double scalar)
{
return (*this = (*this / scalar));
}



// The following are the same,
// but three ways to use.
Vec3 operator-(void)
{
return Vec3(-x, -y, -z);
}


Vec3 Invert(void)
{
return Vec3(-x, -y, -z);
}


Vec3 Reverse(void)
{
return Vec3(-x, -y, -z);
}


double Dot(const Vec3 &a)
{
return (x * a.x + y * a.y + z * a.z);
}


// The following are the same,
// but two ways to use.
Vec3 operator*(const Vec3 &a)
{
return Vec3( y * a.z - z * a.y,
z * a.x - x * a.z,
x * a.y - y * a.x );
}


Vec3 Cross(const Vec3 &a)
{
return Vec3( y * a.z - z * a.y,
z * a.x - x * a.z,
x * a.y - y * a.x );
}


double Length(void)
{
return sqrt(x * x + y * y + z * z);
}


double LengthSquared(void)
{
return (x * x + y * y + z * z);
}



Vec3 Normalize(void)
{
double length = Length();
double X = x;
double Y = y;
double Z = z;

X /= length;
Y /= length;
Z /= length;

return Vec3(X,Y,Z);
}


Vec3 Unit(void)
{
double length = Length();
double X = x;
double Y = y;
double Z = z;

X /= length;
Y /= length;
Z /= length;

return Vec3(X,Y,Z);
}


double Distance(const Vec3 &a)
{
double X = a.x - x;
double Y = a.y - y;
double Z = a.z - z;

return sqrt(X * X + Y * Y + Z * Z);
}

double DistanceSquared(const Vec3 &a)
{
double X = a.x - x;
double Y = a.y - y;
double Z = a.z - z;

return (X * X + Y * Y + Z * Z);
}


bool operator==(const Vec3 &a)
{
return (a.x == x && a.y == y && a.z == z);
}


bool operator!=(Vec3 &a)
{
return !(a == *this);
}


Vec3 Lerp( const Vec3 &b, double t) //const Vec3 &a,
{
double X = x + t*(b.x - x);
double Y = y + t*(b.y - y);
double Z = z + t*(b.z - z);
return Vec3(X,Y,Z);
}


Vec3 Lerp( const Vec3 &a, const Vec3 &b, double t)
{
x = a.x + t*(b.x - a.x);
y = a.y + t*(b.y - a.y);
z = a.z + t*(b.z - a.z);
return *this;
}


Vec3 Maximize(const Vec3 &a)
{
if (x < a.x) x = a.x ;
if (y < a.y) y = a.y ;
if (z < a.z) z = a.z ;
return *this;
}


Vec3 Minimize(const Vec3 &a)
{
if (x > a.x) x = a.x ;
if (y > a.y) y = a.y ;
if (z > a.z) z = a.z ;
return *this;
}


string ToString()
{
char t[_CVTBUFSIZE];
sprintf( t,"%f, %f, %f", x, y, z );
return (t);
}


string XToString(void)
{
char t[_CVTBUFSIZE];
sprintf( t,"%f", x);
return (t);
}


string YToString(void)
{
char t[_CVTBUFSIZE];
sprintf( t,"%f", y );
return (t);
}


string ZToString(void)
{
char t[_CVTBUFSIZE];
sprintf( t,"%f", z );
return (t);
}


void Print(void)
{
cout << x << ", " << y << ", " << z << endl;
}


void Print(const string &s)
{
cout << s << x << ", " << y << ", " << z << endl;
}


private:
double x, y, z;
};



// These are helper functions, they start with lower case letters
void print(const string &s, const double d)
{
cout << s << d << endl;
}


void print(const string &s)
{
cout << s << endl;
}


void print(const double d)
{
cout << d << endl;
}


void print(void)
{
cout << endl;
}


void print(const Vec3 &a)
{
cout << a.GetX() << ", " << a.GetY() << ", " << a.GetZ() << endl;
}


void print(const string s, const Vec3 &a)
{
cout << s << a.GetX() << ", " << a.GetY() << ", " << a.GetZ() << endl;
}

static Vec3 lerp(const Vec3 &a, const Vec3 &b, double t)
{
Vec3 c;
c.SetX(a.GetX() + t*(b.GetX() - a.GetX()));
c.SetY(a.GetY() + t*(b.GetY() - a.GetY()));
c.SetZ(a.GetZ() + t*(b.GetZ() - a.GetZ()));
return c;
}


static Vec3 maximize(const Vec3 &a, const Vec3 &b)
{
Vec3 c;
c.SetX((( a.GetX() > b.GetX()) ? a.GetX() : b.GetX()));
c.SetY((( a.GetY() > b.GetY()) ? a.GetY() : b.GetY()));
c.SetZ((( a.GetZ() > b.GetZ()) ? a.GetZ() : b.GetZ()));
return c;
}


static Vec3 minimize(const Vec3 &a, const Vec3 &b)
{
Vec3 c;
c.SetX((( a.GetX() > b.GetX()) ? b.GetX() : a.GetX()));
c.SetY((( a.GetY() > b.GetY()) ? b.GetY() : a.GetY()));
c.SetZ((( a.GetZ() > b.GetZ()) ? b.GetZ() : a.GetZ()));
return c;
}


#endif // VEC3_H

[danbaron]

Wow, you made a nice class, Kent.

And, it's clear!

:evil: :twisted:

[kryton9]

Thanks Dan. There is a trick I have seen that I have never worked with before. You use a Union of an array and it occupies the same space in memory as the x, y, z variables in the class.

OpenGL as lots of places where it can use arrays as parameters and so I need to figure that out.

I have been experimenting with oxygen, Charle's language. I really love the syntax and so I am slowly experimenting with it. Being in Alpha stages of development, you need to go though the sources to figure things out... so it slow going for me, but the syntax and clever stuff that I see Charle's has in it are too good to walk away from.

Aurel has ported his editor over for it and I use that, it is called OxyEdit.

Hope to see you tinkering with it some day. You come up with clever things to show and educate with in a very nice easy to understand way.

[ErosOlmi]

Some time ago I posted this thread: http://www.thinbasic.com/community/showthread.php?8917-String-library-comparison&highlight=string
It points to a nice C/C++ string comparison page where many libs and classes handling dynamic strings are compared.

In particular have a look at this library http://bstring.sourceforge.net/

Ciao
Eros

[danbaron]

I have a vague idea of what unions are. I have never used them. I guess in the general case, a person will not learn something until he sees a use for it.

Usually, the more documentation there is for a language, the more likely I am to use it. I have a lot of C books, so, I feel empowered to find everything you can do with it.

When a language is first created, it is usually the work of one or a few people. Often then, it is quite limited compared to more mature languages. I guess a language becomes mature when a lot of people start using it. Then, more people begin to develop it, and it begins to get a lot of documentation. It creates its own momentum. I have to admire developers who make their own languages. I think it is a difficult, often thankless quest, with no guarantees at all.

Probably, Powerbasic would be well-suited to use to work with big integers. But, I am hesitant to use it, I'm not sure exactly why. Maybe because it is proprietary. Maybe because the only documentation is its electronic help system.

--------------------------------------------

Now I see Eros' post about "bstring".

It looks good - I think I heard of it previously.

In standard C, I think the implementation should be called, "wstring", for, "worse string".

[danbaron]

In C, if you define a char array with a pointer, then you can't access its individual chars.

For instance,

char* num1 = (char *) malloc(50);
num1 = "27875645366748";

Now, I cannot access any of num1's digits.

I can change num1's value,

num1 = "4758264";

but, it seems that is about all I can do.

So, apparently, numbers defined this way are useless for doing arithmetic with.

There is a way around this problem.

If you define global static char arrays (registers), like

char areg[10000];
char breg[10000];
char creg[10000];

Then, by using them with the dynamic char arrays, you can do arithmetic.

You can index the elements of the registers like in normal arrays - which they are.

Basically, you copy the contents of a dynamic array into a register, do the arithmetic, and then copy the result back into the dynamic array.

Using this method, you would define probably, 3 big registers to do the arithmetic, two for the operands, and one for the result.

And you would allocate as many dynamic arrays as you needed, to represent number variables.

The memory allocated for each variable would be its exact number of digits in bytes (plus one).

Here is the difference between what you can do with pointer char arrays and what you can do with static char arrays: -->

You can assign a value to a pointer char array, but you cannot access its individual elements.

num1 = "3452768"; // OK.
num1[2] = ...; // PROGRAM CRASH.

You can access the individual elements of a static char array, but you cannot assign a value to it (except by assigning values to each individual element).

areg[3] = 5; // OK.
areg = "436783467"; // WON'T COMPILE.

I'm not saying this is a good way to do arithmetic using char arrays, but, it's a way.

To demonstrate the general idea, below, a value is assigned to num1, and then its digits are reversed.

:( :p


' code -------------------------------------------------------------------------------------------------------------------------------------------

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

#define short unsigned short int
#define long unsigned long int
#define maxdigits 10000

//-------------------------------------------------------------------------------------------------------

char areg[maxdigits + 1];
char breg[maxdigits + 1];
char creg[maxdigits + 1];

//-------------------------------------------------------------------------------------------------------

char* makechararray(long nchars)
{
return (char *) malloc(nchars);
}

//-------------------------------------------------------------------------------------------------------

long chararraylength(char* chararray)
{
return strlen(chararray) + 1;
}

//-------------------------------------------------------------------------------------------------------

void copymemory(char* from, char* to)
{
long copylength = chararraylength(from);
memcpy(to, from, copylength);
}

//-------------------------------------------------------------------------------------------------------

void changechararray(char* change, char* tothis)
{
long newsize = chararraylength(tothis);
realloc(change, newsize);
copymemory(tothis, change);
}

//-------------------------------------------------------------------------------------------------------

void reversecopyreg(char* regtocopy, char* tempreg, char* copyto)
{
long i;
long copylength = chararraylength(regtocopy) - 1;
for(i=1; i<=copylength; i++) tempreg[copylength - i] = regtocopy[i - 1];
tempreg[copylength] = regtocopy[copylength];
changechararray(copyto, tempreg);
}

//-------------------------------------------------------------------------------------------------------

int main()
{
int maxchars = 1000;
char* numbuffer;
char* num1;
int numbufferlength;

numbuffer = makechararray(maxchars);

numbuffer = "79857387940275396856641092";
numbufferlength = chararraylength(numbuffer);

num1 = makechararray(numbufferlength);

copymemory(numbuffer, num1);

printf("num1 = %s\n", num1);

copymemory(num1, areg);

reversecopyreg(areg, breg, num1);
printf("num1 = %s\n", num1);

return 0;
}

' output -----------------------------------------------------------------------------------------------------------------------------------------

num1 = 79857387940275396856641092
num1 = 29014665869357204978375897
Press any key to continue...