Problems with big integers and some Hollywood operators

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

Problems with big integers and some Hollywood operators

Post by Allanon »

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! :D

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")
User avatar
Allanon
Posts: 732
Joined: Sun Feb 14, 2010 7:53 pm
Location: Italy
Contact:

Re: Problems with big integers and some Hollywood operators

Post by Allanon »

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))
User avatar
airsoftsoftwair
Posts: 5433
Joined: Fri Feb 12, 2010 2:33 pm
Location: Germany
Contact:

Re: Problems with big integers and some Hollywood operators

Post by airsoftsoftwair »

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?!
User avatar
Allanon
Posts: 732
Joined: Sun Feb 14, 2010 7:53 pm
Location: Italy
Contact:

Re: Problems with big integers and some Hollywood operators

Post by Allanon »

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 :)

About the modulo:
1. Calculator online : link
2. Another one with an explanation about the results : link
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.
User avatar
airsoftsoftwair
Posts: 5433
Joined: Fri Feb 12, 2010 2:33 pm
Location: Germany
Contact:

Re: Problems with big integers and some Hollywood operators

Post by airsoftsoftwair »

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.
User avatar
Allanon
Posts: 732
Joined: Sun Feb 14, 2010 7:53 pm
Location: Italy
Contact:

Re: Problems with big integers and some Hollywood operators

Post by Allanon »

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 :)
User avatar
airsoftsoftwair
Posts: 5433
Joined: Fri Feb 12, 2010 2:33 pm
Location: Germany
Contact:

Re: Problems with big integers and some Hollywood operators

Post by airsoftsoftwair »

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
User avatar
Allanon
Posts: 732
Joined: Sun Feb 14, 2010 7:53 pm
Location: Italy
Contact:

Re: Problems with big integers and some Hollywood operators

Post by Allanon »

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
:)
User avatar
airsoftsoftwair
Posts: 5433
Joined: Fri Feb 12, 2010 2:33 pm
Location: Germany
Contact:

Re: Problems with big integers and some Hollywood operators

Post by airsoftsoftwair »

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 ;)
User avatar
Allanon
Posts: 732
Joined: Sun Feb 14, 2010 7:53 pm
Location: Italy
Contact:

Re: Problems with big integers and some Hollywood operators

Post by Allanon »

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 :D

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 :lol:
Post Reply