## Problems with big integers and some Hollywood operators

Report any Hollywood bugs here
Allanon
Posts: 636
Joined: Sun Feb 14, 2010 7:53 pm
Location: Italy
Contact:

### Problems with big integers and some Hollywood operators

I'm having trobles porting a pure Lua library to implement the HMAC-SHA256 that I need to authenticate requests to communicate with a server, so I started to convert it but when has come the time for a test I got errors and wrong numbers here and there.

After long debug sessions I've found several problems with the % operator and its conterpart Mod(), I also had trouble using Int(), << >> operators and Shl() and Shr() with big numbers.

For example:

Code: Select all

``````Mod(12345679123, 234567) returns 183346
12345679123 % 234567 returns -22763
``````

There are several cases where big numbers behaves strange, I feel that they are represented in several ways internally and converted
on the fly by Hollywood depending on the cases, I remember to have found something like the following during my tests (numbers are invented, because I don't remember the original ones):

Code: Select all

``````Local a = b / c
DebugPrint(a)  ; -> 123343.98
Local aa
aa = a
DebugPrint(aa) ; -> 123344
``````

When I saw that I jumped on my chair!

Here is a little script with some tests so you have an example of what I remember to have encountered in these two days of panic.

Code: Select all

``````; Very basic and slow mod routine to test the builtin one
Function mymod(a, b)
Local aa = a
While aa > b
aa = aa - b
Wend
Return(aa)

EndFunction

Local values   = { 1, 123, 123456, 123456789, 12345679123, 123456789134 }
Local dividers = { 2648, 25534, 234567, 234567890, 23456790123, 234567901245 }

Local t = ListItems(values)-1

For Local i = 0 To t
Local v1 = values[i]
For Local ii = 0 To t
Local v2 = dividers[ii]
DebugPrint("VALUES: " .. v1 .. ", " .. v2)
Local r1 = Mod(v1, v2)
Local r2 = v1 % v2
Local r3 = mymod(v1, v2)
DebugPrint("| MOD() = " .. r1)
DebugPrint("|     % = " .. r2)
DebugPrint("| MYMOD = " .. r3)
If r1 <> r2 Or r1 <> r3 Or r2 <> r3 Then DebugPrint("| *** ERROR ***\n")
Next
Next

DebugPrompt("PROCEED WITH INT()  - Hit Enter")
For Local i = 0 To t
Local v = values[i]
Local r = Int(v)
DebugPrint("| VALUE: ", v)
DebugPrint("| INT(): ", r)
DebugPrint("| CAST : ", Cast(Int(v), False, #INTEGER))
If v <> r Then DebugPrint("| *** ERROR ***\n")
Next

DebugPrompt("PROCEED WITH SHIFT >> And DIVISION  - Hit Enter")
Local a = 1385294725120
Local c = 255548
DebugPrint("Testing only these two values: ", a, ", ", b)
For Local bit = 1 To 24 Step 2
Local b = 2^bit
DebugPrint(bit .. " BITs = " .. 2^bit)
DebugPrint("  Division   : " .. a .. " / " .. b .. " = " .. a/b)
DebugPrint("  Shift Right: " .. a .. " >> " .. bit .. " = " .. a>>bit)
DebugPrint("---")
DebugPrint("  Division   : " .. c .. " / " .. b .. " = " .. c/b)
DebugPrint("  Shift Right: " .. c .. " >> " .. bit .. " = " .. c>>bit)
DebugPrint("--- --- ---")
Next

DebugPrompt("Hit Enter to Close")
``````
----------------------------
[Allanon] Fabio Falcucci
AMC - Creative Development // Docs Site // Support Forum
Support me on Patreon for Hollywood libraries!

Allanon
Posts: 636
Joined: Sun Feb 14, 2010 7:53 pm
Location: Italy
Contact:

### Re: Problems with big integers and some Hollywood operators

Found another wrong behaviour:

Code: Select all

``````Local a = -10225030983111
Local d = 2^24
DebugPrint(Mod(a, d))
``````
It prints

Code: Select all

``-5696967``
but it is wrong!!

The correct answer should be : 11080249

Infact using a trick to calculate the modulo of negative numbers the result is right:

Code: Select all

``````Local a = -10225030983111
Local d = 2^24

DebugPrint(d-Mod(-a, d))
``````
----------------------------
[Allanon] Fabio Falcucci
AMC - Creative Development // Docs Site // Support Forum
Support me on Patreon for Hollywood libraries!

airsoftsoftwair
Posts: 4350
Joined: Fri Feb 12, 2010 2:33 pm
Location: Germany
Contact:

### Re: Problems with big integers and some Hollywood operators

Yes, the % and \ operators as well as the Int() function all converted their operands to signed 32-bit. I have fixed this now:

Code: Select all

``````- Fix: The modulo (%) and integer division (\) operators as well as the Int() command always converted all
operands to signed 32-bit; they now use signed 64-bit integers instead
``````
Making bitwise operators like >> and << support big numbers is not really possible, though, because Hollywood doesn't have a 64-bit integer type. All numbers in Hollywood are stored as 64-bit floating point values, making 2^53 the largest integer that can be stored in a Hollywood variable, whereas a 64-bit integer can obviously store 2^64-1. So it wouldn't be possible for Hollywood to offer full 64-bit bitwise operations. Of course, the bitwise operators could be extended to support more than 32 bits but definitely not the full 64 bits. That's why I rather keep them like they are because it's more consistent to have them limited to 32 bits than to some odd 53 bits or something.

Also, extending the bitwise operators to more than 32 bits would introduce all sorts of compatibility issues, e.g. shifting (\$80000000<<1) is 0 in 32-bit mode but when using 64-bit integers it is obviously \$100000000 so we would need a new command to enable 64-bit bitwise operations but once again, they would be limited to 53 bits so it would be rather odd. Lua had pretty much the same problem and this was solved in Lua 5.3 in 2015 by re-designing the way Lua stored numbers so that there is a real 64-bit integer type now but this is all very difficult to backport to Hollywood so I think we have to live with bitwise operations being limited to 32 bits.
Allanon wrote:
Wed Jul 08, 2020 5:37 pm
Found another wrong behaviour:

Code: Select all

``````Local a = -10225030983111
Local d = 2^24
DebugPrint(Mod(a, d))
``````
It prints

Code: Select all

``-5696967``
but it is wrong!!

The correct answer should be : 11080249
Huh? Why? My calculator returns -569697 as well so I don't see why this should be wrong?!

Allanon
Posts: 636
Joined: Sun Feb 14, 2010 7:53 pm
Location: Italy
Contact:

### Re: Problems with big integers and some Hollywood operators

Ok, for the << >> operators, I can use the division/multiplication even if it is slower but the fact is that I didn't know how they was implemented thinking (wrongly) that all #NUMBERS was treated/stored in the same way

3. My Windows calculator gives me the positive result.

Digging a bit in Internet seems that both results (positive and negative ones) are correct, the calculator on point 2 says the following:
If the dividend or divisor is negative, then two possible choices for the remainder occur. In mathematics, the remainder is positive, but implementations in programming languages differ.
----------------------------
[Allanon] Fabio Falcucci
AMC - Creative Development // Docs Site // Support Forum
Support me on Patreon for Hollywood libraries!

airsoftsoftwair
Posts: 4350
Joined: Fri Feb 12, 2010 2:33 pm
Location: Germany
Contact:

### Re: Problems with big integers and some Hollywood operators

Allanon wrote:
Thu Jul 09, 2020 4:37 pm
Ok, for the << >> operators, I can use the division/multiplication even if it is slower but the fact is that I didn't know how they was implemented thinking (wrongly) that all #NUMBERS was treated/stored in the same way
Yeah, the manual leaves a little to be desired here but I didn't want to confuse the reader
Allanon wrote:
Thu Jul 09, 2020 4:37 pm
3. My Windows calculator gives me the positive result.
Which Windows version? On Windows 7 I get the negative result... same as Hollywood.

Allanon
Posts: 636
Joined: Sun Feb 14, 2010 7:53 pm
Location: Italy
Contact:

### Re: Problems with big integers and some Hollywood operators

I'm on WIndows 10, but if you look at the link nr.2 they say that both results are valid even if the positive one is more mathematics-friendly.
Every online calculator I found returned the positive result, I'm not too into deep-math-stuff
----------------------------
[Allanon] Fabio Falcucci
AMC - Creative Development // Docs Site // Support Forum
Support me on Patreon for Hollywood libraries!

airsoftsoftwair
Posts: 4350
Joined: Fri Feb 12, 2010 2:33 pm
Location: Germany
Contact:

### Re: Problems with big integers and some Hollywood operators

Lua also returns the negative number. Paste the following code here:

Code: Select all

``````local a = -10225030983111
local d = 2^24
print(math.fmod(a,d))
``````
Output:

Code: Select all

``````-5696967.0
``````

Allanon
Posts: 636
Joined: Sun Feb 14, 2010 7:53 pm
Location: Italy
Contact:

### Re: Problems with big integers and some Hollywood operators

Yep, but if you use % :

Code: Select all

``````local a = -10225030983111
local d = 2^24
print(a % d)
``````
You get:

Code: Select all

``````11080249.0
``````
----------------------------
[Allanon] Fabio Falcucci
AMC - Creative Development // Docs Site // Support Forum
Support me on Patreon for Hollywood libraries!

airsoftsoftwair
Posts: 4350
Joined: Fri Feb 12, 2010 2:33 pm
Location: Germany
Contact:

### Re: Problems with big integers and some Hollywood operators

Yeah, when using the % operator, Lua does more than what math.fmod() does:

Code: Select all

``````/*
** modulo: defined as 'a - floor(a/b)*b'; the direct computation
** using this definition has several problems with rounding errors,
** so it is better to use 'fmod'. 'fmod' gives the result of
** 'a - trunc(a/b)*b', and therefore must be corrected when
** 'trunc(a/b) ~= floor(a/b)'. That happens when the division has a
** non-integer negative result: non-integer result is equivalent to
** a non-zero remainder 'm'; negative result is equivalent to 'a' and
** 'b' with different signs, or 'm' and 'b' with different signs
** (as the result 'm' of 'fmod' has the same sign of 'a').
*/
#if !defined(luai_nummod)
#define luai_nummod(L,a,b,m)  \
{ (void)L; (m) = l_mathop(fmod)(a,b); \
if (((m) > 0) ? (b) < 0 : ((m) < 0 && (b) > 0)) (m) += (b); }
#endif
``````
I.e. if the result is negative and the divisor is positive, the divisor is added to the result which then results in 11080249. I don't know about the mathematical background here but I can't change it in Hollywood anyway because it would break scripts that depend on the old behaviour. So you could just apply the math above if you want to have the different result

Allanon
Posts: 636
Joined: Sun Feb 14, 2010 7:53 pm
Location: Italy
Contact:

### Re: Problems with big integers and some Hollywood operators

There is no problem adapting the code for me now that I know the problems
When you have to port something like this and you start getting thousand of errors in your face, the debug sessions become hell

I suggest you to document how math works on Hollywood and to specify when there are differences between operators and the relative commands,I lost the few hair left in my head over the last week
----------------------------
[Allanon] Fabio Falcucci
AMC - Creative Development // Docs Site // Support Forum
Support me on Patreon for Hollywood libraries!