A89: Re: TIOS int format

[Prev][Next][Index][Thread]

A89: Re: TIOS int format

Hi!

> How does TIOS store and reference integers?

1. Bytes of the integer in little endian;
2. The number of bytes occupied by integer (one byte);
3. POSINT_TAG or NEGINT_TAG, depending of the sign.

These integers are kept on the expressions stack, or in TI-Basic
variables (of course, in TI-Basic variables, there are two length
bytes at the begining).

> In other words, getting to the root of my inquiry, what would be the C
> structure that would be used to represent any arbitrarily-long binary
> integer?

Such structure is similar like BN structure defined in rsa.h, except
the length byte is at the end, not at the begining (because estack data
is always in RPN). So, such structure can't be strictly represented
using C syntax, because it requires something as

struct big_int
{
  BYTE data[size];   // but size is not known in advance
  BYTE size;
  BYTE tag;
}

> Also, how would two extermely long binary integers be multiplied and
> divided? Does TIOS have its own binary (hex? larger base?) multiplication
> routine somewhere in the ROM?  Something that works similarly to BCD
> multiplication/division, I'm guessing?

Such routines surely exist in TIOS, but the strange fact is that such
routines are not in TIOS jump table (read: they are not usable). However,
two routines ARE in TIOS jump table: for calculating (A*B)%N and (A^B)%N
where "%" is "modulus" operation, because they are used in RSA
cryptosystem.
Both of them are defined in rsa.h header file. They may be used for 
multiplying and raising to the power: you always can set N to very big 
number, then (A*B)%N=A*B. Also, you can use them for calculating modulus
(if you set B=1). But, I am not sure how you can  simulate division. I 
think that TI never use integer division: everything like A/B is kept as
a fraction, except in approx mode; TIOS then uses NG_approxESI.

> And how long is type "long long" on GCC-68k?  How are those
> multiplied/divided/etc when compiled?

long long is 8 bytes. Multiplying and dividing longlongs are not
open-coded but require library routines (like "longmul" patch, etc.).
I am thinking about writing such routines too.

By the way, I wrote a small program which ilustrates operations with
big integers. I uploaded it on ticalc before 5 days, but it is still
not present in the archive. It may be interesting for 89 programmers,
so I will attach it to this message. Sorry for posting binaries, but
it may be useful for a lot of programmers...

Cheers,

Zeljko Juric

powmod89.zip (ZipFolders)