Dealing with a large integer

[yong]

I rewrite my code but the uint64_t seems can't work well.

The code is here:
========================
#include <stdio.h>
#include <stdint.h>
#include "compress.h"

int main()
{
struct code6 mycode6;
struct code5 mycode5;

mycode6.item1=1;
mycode6.item2=2;
mycode6.item3=3;
mycode6.item4=4;
mycode6.item5=5;
mycode6.item6=6;

mycode5=codecompress(mycode6);

printf("mycode5.item1 is: %d\n",mycode5.item1);
printf("mycode5.item2 is: %d\n",mycode5.item2);
printf("mycode5.item3 is: %d\n",mycode5.item3);
printf("mycode5.item4 is: %d\n",mycode5.item4);
printf("mycode5.item5 is: %d\n",mycode5.item5);

return 0;
}
========================

and the compress.h is here:

========================
#include <stdint.h>

struct code6
{
unsigned long item1;
unsigned long item2;
unsigned long item3;
unsigned long item4;
unsigned long item5;
unsigned long item6;
};

struct code5
{
unsigned long item1;
unsigned long item2;
unsigned long item3;
unsigned long item4;
unsigned long item5;
};

struct code5 codecompress(struct code6 origcode)
{
struct code5 ret;
uint64_t math64;

math64=origcode.item1*(256^5)+origcode.item2*(256^4)+origcode.item3*(256^3)+origcode.item4*(256^2)+origcode.item5*256+origcode.item6;
printf("math64 is: %X\n",math64);

ret.item5=(math64)%(uint64_t)900;
math64/=900;
ret.item4=(math64)%900;
math64/=900;
ret.item3=(math64)%900;
math64/=900;
ret.item2=(math64)%900;
math64/=900;
ret.item1=(math64)%900;

return ret;
}

========================

After the code runs it displays that

------------------------
math64 is: F24
mycode5.item1 is: 0
mycode5.item2 is: 0
mycode5.item3 is: 0
mycode5.item4 is: 4
mycode5.item5 is: 276

 

[Walter Roberson]

I rewrite my code but the uint64_t seems can't work well.

Unfortunately you did not quote any of the original task.

The code is here:

math64=origcode.item1*(256^5)+origcode.item2*(256^4)+origcode.item3*(256^3)+origcode.item4*(256^2)+origcode.item5*256+origcode.item6;

In C, the ^ operator is "Exclusive OR". In your description of
the original task, I would be surprised if your use of ^
did not indicate exponentiation there.

In C, 256 to the power
of 0 is 1
of 1 is 1<<8
of 2 is 1<<16
of 3 is 1<<24
of 4 is 1<<32
of 5 is 1<<40

On most systems, 1<<32 is bigger than an unsigned long will hold.
C89 does not promise that anything from 1<<32 upwards is available.
C99 does provide unsigned long long for that purpose, but you
must be careful to avoid accidently working in narrower types
in an intermediate stage.

You do not actually need to use the multiplications or additions
in your calculation of math64. Presuming C99, your code could instead be

math64 = (unsigned long long) origcode.item1 << 40 |
(unsigned long long) origcode.item2 << 32 |
(unsigned long long) origcode.item3 << 24 |
(unsigned long long) origcode.item4 << 16 |
(unsigned long long) origcode.item5 << 8 |
(unsigned long long) origcode.item6;

 

[yong]

Unfortunately you did not quote any of the original task.





In C, the ^ operator is "Exclusive OR". In your description of
the original task, I would be surprised if your use of ^
did not indicate exponentiation there.

In C, 256 to the power
of 0 is 1
of 1 is 1<<8
of 2 is 1<<16
of 3 is 1<<24
of 4 is 1<<32
of 5 is 1<<40

On most systems, 1<<32 is bigger than an unsigned long will hold.
C89 does not promise that anything from 1<<32 upwards is available.
C99 does provide unsigned long long for that purpose, but you
must be careful to avoid accidently working in narrower types
in an intermediate stage.

You do not actually need to use the multiplications or additions
in your calculation of math64. Presuming C99, your code could instead be

math64 = (unsigned long long) origcode.item1 << 40 |
(unsigned long long) origcode.item2 << 32 |
(unsigned long long) origcode.item3 << 24 |
(unsigned long long) origcode.item4 << 16 |
(unsigned long long) origcode.item5 << 8 |
(unsigned long long) origcode.item6;

I rewrite my code and it seems run correctly now.

main.c
===================
#include <stdio.h>
#include <stdint.h>
#include <math.h>
#include "compress.h"

int main()
{
struct code6 mycode6;
struct code5 mycode5;

mycode6.item1=1;
mycode6.item2=2;
mycode6.item3=3;
mycode6.item4=4;
mycode6.item5=5;
mycode6.item6=6;

mycode5=codecompress(mycode6);

printf("mycode5.item1 is: %d\n",mycode5.item1);
printf("mycode5.item2 is: %d\n",mycode5.item2);
printf("mycode5.item3 is: %d\n",mycode5.item3);
printf("mycode5.item4 is: %d\n",mycode5.item4);
printf("mycode5.item5 is: %d\n",mycode5.item5);

return 0;
}
===================

compress.h
===================
#include <stdint.h>

struct code6
{
unsigned long item1;
unsigned long item2;
unsigned long item3;
unsigned long item4;
unsigned long item5;
unsigned long item6;
};

struct code5
{
unsigned long item1;
unsigned long item2;
unsigned long item3;
unsigned long item4;
unsigned long item5;
};

struct code5 codecompress(struct code6 origcode)
{
struct code5 ret;
uint64_t math64;

math64=origcode.item1*((uint64_t)pow(256,5))+origcode.item2*((uint64_t)pow(256,4))+origcode.item3*((uint64_t)pow(256,3))+origcode.item4*((uint64_t)pow(256,2))+origcode.item5*256+origcode.item6;

ret.item5=(math64)%(uint64_t)900;
math64/=900;
ret.item4=(math64)%900;
math64/=900;
ret.item3=(math64)%900;
math64/=900;
ret.item2=(math64)%900;
math64/=900;
ret.item1=(math64)%900;

return ret;
}
===================


Thank you all. :]

 

[ena8t8si]

I'm using linux.And I found another variable type named uint64_t
in stdint.h which represents a 64bit integer.It's seems not
standard but very useful.

Actually, that is standard as of the latest standard. From the C99
draft standard:

7.18.1.1 Exact-width integer types

[#2] The typedef name uintN_t designates an unsigned integer
type with width N. Thus, uint24_t denotes an unsigned
integer type with a width of exactly 24 bits.

An implementation is not required to provide them.

Actually, under C99, if the underlying hardware has such objects
the implementation must then support them. Otherwise they can be
omitted.

If you read the relevant paragraph in the standard,
you'll see that it doesn't say anything about the
underlying hardware. It's perfectly legal for an
implementation to have 8 bit chars, 16 bit shorts,
and 64 bit ints, longs and long longs, and not define
int32_t, regardless of what hardware it's running on.

 

[Jordan Abel]

yong wrote:

I'm using linux.And I found another variable type named uint64_t
in stdint.h which represents a 64bit integer.It's seems not
standard but very useful.

Actually, that is standard as of the latest standard. From the C99
draft standard:

7.18.1.1 Exact-width integer types

[#2] The typedef name uintN_t designates an unsigned integer
type with width N. Thus, uint24_t denotes an unsigned
integer type with a width of exactly 24 bits.

An implementation is not required to provide them.

Actually, under C99, if the underlying hardware has such objects
the implementation must then support them. Otherwise they can be
omitted.

If you read the relevant paragraph in the standard,
you'll see that it doesn't say anything about the
underlying hardware. It's perfectly legal for an
implementation to have 8 bit chars, 16 bit shorts,
and 64 bit ints, longs and long longs, and not define
int32_t, regardless of what hardware it's running on.

I think his claim is that the types have to be available if the relevant
standard types are twos-complement and have no padding. I don't know if
that's true or not. "hardware" is just a shorthand for "whatever the
'native' types are implemented on."

*wonders why int24_t isn't required if there is a type with 24 bits, no
padding bits, and twos complement representation*

 

[Me]

I have an large integer in this format

x1*256^5 + x2*256^4 + x3*256^3 + x4*256^2 + x5*256 + x6
now I must convert it to this format
y1*900^4 + y2*900^3 + y3*900^2 + y4*900 + y5

x1-x5 is given.I must get y1-y4 from it.

How can I do this on my 32bit PC?

It looks like you're trying to convert a base-256 number to a base-900
number (i.e. all the the xN's are in the range [0, 255]). If this is
the case, then you can do this:

unsigned long long x = x1;
x = x<<8 | x2;
x = x<<8 | x3;
x = x<<8 | x4;
x = x<<8 | x5;

And then to get y1..y5:

y5 = x % 900; x /= 900;
y4 = x % 900; x /= 900;
y3 = x % 900; x /= 900;
y2 = x % 900; x /= 900;
y1 = x;

 

[russell kym horsell]

Hi all
I have an large integer in this format [lemm call this X:]
x1*256^5 + x2*256^4 + x3*256^3 + x4*256^2 + x5*256 + x6
now I must convert it to this format [Y:]
y1*900^4 + y2*900^3 + y3*900^2 + y4*900 + y5
x1-x5 is given.I must get y1-y4 from it.
How can I do this on my 32bit PC?
Sorry for that my English is poor.
Thanks.

Some kind of pdf encoder, eh?


There's probably a lot of literature on smart tricks, but
the basic idea (beside simply using 64-bit integers and brute force --
BTW even 32-bit PC's can do h/w 64-bit arith these days) is to note that

X % 900 = Y % 900 = y4.

Then we see that
256^5 % 900 = 376
256^4 % 900 = 796
256^3 % 900 = 316
256^2 % 900 = 736
256^1 % 900 = 256

So we must have y4 = (376*x1 + 796*x2 + 316*x3 + 736*x4 + 256*x5 + x6) % 900 .
(Look, maw, only 16-bit arithmetic!)

Similiarly for the other y_i.

 

[James Dow Allen]

it is possible for a program to know how long the resulting string from
a sprintf statement will be. if that was a dig at the recent gets
debate, keep in mind it is NOT possible for a program to know how much
the user will type.

Sigh. It sounds like we need to beat the dead horse one more time.

The gets() which I defended gots'ed a string which my own software
had printf'ed. Got it?

James

 

[Jordan Abel]

Sigh. It sounds like we need to beat the dead horse one more time.

The gets() which I defended gots'ed a string which my own software
had printf'ed. Got it?

How did you guarantee this? There is no mechanism in the standard to
ensure that this happens. If gets is removed from the standard, systems
which _do_ provide such a mechanism may provide gets as an extension.

 

[ena8t8si]

Default User wrote:
yong wrote:

I'm using linux.And I found another variable type named uint64_t
in stdint.h which represents a 64bit integer.It's seems not
standard but very useful.

Actually, that is standard as of the latest standard. From the C99
draft standard:

7.18.1.1 Exact-width integer types

[#2] The typedef name uintN_t designates an unsigned integer
type with width N. Thus, uint24_t denotes an unsigned
integer type with a width of exactly 24 bits.

An implementation is not required to provide them.

Actually, under C99, if the underlying hardware has such objects
the implementation must then support them. Otherwise they can be
omitted.

If you read the relevant paragraph in the standard,
you'll see that it doesn't say anything about the
underlying hardware. It's perfectly legal for an
implementation to have 8 bit chars, 16 bit shorts,
and 64 bit ints, longs and long longs, and not define
int32_t, regardless of what hardware it's running on.

I think his claim is that the types have to be available if the relevant
standard types are twos-complement and have no padding. I don't know if
that's true or not. "hardware" is just a shorthand for "whatever the
'native' types are implemented on."

If that's the claim that was intended then someone needs
a lesson in writing for clarity.

I find it more likely that your reading is simply overly
charitable. There was no mention, for example, of twos
complement in the original message.

 

[Jordan Abel]

If that's the claim that was intended then someone needs
a lesson in writing for clarity.

I find it more likely that your reading is simply overly
charitable. There was no mention, for example, of twos
complement in the original message.

It's implied in "such objects".

 

[ena8t8si]

It's implied in "such objects".

Only to someone who already knows what the Standard
says, since twos complement isn't mentioned in any
message in the thread before yours. Obviously, someone
who is writing to explain what the standard says is
assuming that his audience doesn't already know what
it says, otherwise there's no point in explaining it.

 

[Mark McIntyre]

How did you guarantee this? There is no mechanism in the standard to
ensure that this happens.

Of course there isn't.

But there's also nothing in the standard that ensures that
fflush(stdout) won't explode a nuclear device. It requires it to clear
the buffer, nothing more. Evaporating the installation would achieve
this handily.

Hyperbole aside, my point is that any part of the standard that
interacts with the outside world is open to abuse. Careful programming
and careful use prevent that, nothing more.

For what its worth I agree, gets() is overly dangerous and it'd be
nice if it were gone. I disagree that its impossible to safely use it.
Its just excessively hard.
Mark McIntyre

 

[Jordan Abel]

Of course there isn't.

But there's also nothing in the standard that ensures that
fflush(stdout) won't explode a nuclear device. It requires it to clear
the buffer, nothing more. Evaporating the installation would achieve
this handily.

Hyperbole aside, my point is that any part of the standard that
interacts with the outside world is open to abuse. Careful programming
and careful use prevent that, nothing more.

For what its worth I agree, gets() is overly dangerous and it'd be
nice if it were gone. I disagree that its impossible to safely use it.
Its just excessively hard.
Mark McIntyre

Post code that you think safely uses gets and i'll prove it wrong within
the context of the API you are using to "ensure" it. [well, i'm hoping
you're using the unix api, since i wouldn't have the first clue about
any other one]

 

[Walter Roberson]

Post code that you think safely uses gets and i'll prove it wrong within
the context of the API you are using to "ensure" it. [well, i'm hoping
you're using the unix api, since i wouldn't have the first clue about
any other one]

How about something like this:

Open a file w+. Write known data into it. fseek() back to the
beginning of the file. gets() with a buffer at least as big as
the data to be written.

Within standard C, there is nothing that could sneak in and change
the file contents "underneath you". Unix has multiprocessing
and another Unix process could change the file, but that's not the
fault of standard C. And besides, you could run this on a system
that did not offer multiple processes. (Now, if you start going
in and bashing The One True Process with a debugger, clearly C
would not be able to offer any guarantees of anything at all.)

 

[Ben Pfaff]

Post code that you think safely uses gets and i'll prove it wrong within
the context of the API you are using to "ensure" it. [well, i'm hoping
you're using the unix api, since i wouldn't have the first clue about
any other one]

How about something like this:

Open a file w+. Write known data into it. fseek() back to the
beginning of the file. gets() with a buffer at least as big as
the data to be written.

gets() reads from stdin. You'll have to use freopen() to replace
stdin by your file. Seems like a pretty big stretch to make just
to use gets() safely, when you could just use a better designed
function instead.

 

[Jordan Abel]

Post code that you think safely uses gets and i'll prove it wrong within
the context of the API you are using to "ensure" it. [well, i'm hoping
you're using the unix api, since i wouldn't have the first clue about
any other one]

How about something like this:

Open a file w+. Write known data into it. fseek() back to the
beginning of the file. gets() with a buffer at least as big as
the data to be written.

gets() reads from stdin. You'll have to use freopen() to replace
stdin by your file. Seems like a pretty big stretch to make just
to use gets() safely, when you could just use a better designed
function instead.

Is it even permissible to change the mode of stdin?

 

[Walter Roberson]

gets() reads from stdin. You'll have to use freopen() to replace
stdin by your file.
True.

Seems like a pretty big stretch to make just
to use gets() safely, when you could just use a better designed
function instead.

Mark's claim is that there exists at least one standards-compliant
system under which at least one standards-complaint program can safely
use gets().

Jordan's claim appears to be that gets() is unsafe for every *possible*
standards-compliant program on every *possible* standards-compliant
environment.

Mark doesn't claim that gets() is safe in every environment or
every program; nor does he claim that the safe program could be
written in (say) less than a million lines of code -- just that
at least one such safe program + environment combination exists.

So... if the safe program involves freopen() on stdin and requires
a single-user mono-tasking environment, then so be it: if it can
be done *at all* then Mark would be right. Mark did say that
it was "excessively hard" to do...

 

[Walter Roberson]

Is it even permissible to change the mode of stdin?

C89 does not have an prohibition against it in the description
of freopen(); it might somewhere else, perhaps.

But in this connection, the footnote is informative:

116. The primary use of the freopen function is to change the
file associated with a standard text stream (stderr, stdin,
or stdout), as those identifiers need not be modifiable lvalues
to which the value returned by the fopen function may be assigned.


I would interpret that as being supportive of changing the mode
as well as the association, in that it talks about providing a
mechanism to essentially assign new values to those predefined
identifiers -- and if one *could* just write to those identifiers
(if they were lvalues) then one could put in a stream of a
different mode.

Of course, my interpretation is not to be considered "proof" ;-)

 

[Jordan Abel]

C89 does not have an prohibition against it in the description
of freopen(); it might somewhere else, perhaps.

But in this connection, the footnote is informative:

116. The primary use of the freopen function is to change the
file associated with a standard text stream (stderr, stdin,
or stdout), as those identifiers need not be modifiable lvalues
to which the value returned by the fopen function may be assigned.


I would interpret that as being supportive of changing the mode
as well as the association, in that it talks about providing a
mechanism to essentially assign new values to those predefined
identifiers -- and if one *could* just write to those identifiers
(if they were lvalues) then one could put in a stream of a
different mode.

Of course, my interpretation is not to be considered "proof" ;-)

My interpretation is the opposite - that it's intended to change stdin
to be _another file_ open in read mode, or stdout/stderr to another file
open in write mode.

It's also possible that on some systems extra magic may be needed to
make a re-opened stdout become the standard output of a command executed
via system(), or even for a re-opened stream to become the standard
stream used by functions not implemented in standard C such as perror().
It also might be desirable for the buffering state of a stream to be
retained in some cases. For example, there is a good reason why stderr
is not fully buffered at program start. (It's unclear to me whether
freopen can even change the buffering state at all - though it could be
desirable to do so when changing stdout to be a regular file when it was
an interactive device at program startup)