4 replies to this topic

[AlgoDump]

Hi,

 

I have been working on a reverse engineering effort for a question posed by Matt Parker:

Youtube: https://www.youtube....h?v=7LKy3lrkTRA

 

I had a breakthrough this xmas, when I found a way to capture the CPU state of the ClassWiz Emulator for fx-83/85GT while evaluating an expression.

Although I have already solved the initial question (all results are divided by pi and multiplied by 25200 and checked for integers) there are many more interesting facts to discover.

I am particularly interested in the mathematics, strategies and algorithms that are used to calculate results.

 

Since I have found a lot of initial ground work on this forum, I thought it would be nice to share the knowledge back with you.

 

The project is long from being finished, and any comments or insights are welcome.

 

Please find the git repository here:

https://bitbucket.or...cpu/src/public/

 

In order to show what it I found, I can show you a small step, where 1771561 is divided by 13.

47253     ADD: 0130000000000000 + 0130000000000000
47272     ADD: 0260000000000000 + 0130000000000000

       177156100000000 
       390000000000000 
SUB   9787156100000000 
 
      9787156100000000 
       130000000000000 
ADD   9917156100000000 
 
      9917156100000000 
       130000000000000 
ADD     47156100000000  Resulting digit: 3-1-1 = 1 
 
       471561000000000 
       390000000000000 
SUB     81561000000000 
 
        81561000000000 
       390000000000000 
SUB   9691561000000000 
 
      9691561000000000 
       130000000000000 
ADD   9821561000000000 
 
      9821561000000000 
       130000000000000 
ADD   9951561000000000 
 
      9951561000000000 
       130000000000000 
ADD     81561000000000  Resulting digit: 3+3-1-1-1 = 3 
 
       815610000000000 
       390000000000000 
SUB    425610000000000 
 
       425610000000000 
       390000000000000 
SUB     35610000000000 
 
        35610000000000 
       390000000000000 
SUB   9645610000000000 
 
      9645610000000000 
       130000000000000 
ADD   9775610000000000 
 
      9775610000000000 
       130000000000000 
ADD   9905610000000000 
 
      9905610000000000 
       130000000000000 
ADD     35610000000000 Resulting digit: 3+3+3-1-1-1 = 6 
 
Etc. (total of 84 subtractions/additions) 
With result: 1.36273923076923 * 10^5

Edited by AlgoDump, 27 February 2021 - 11:55 PM.

[anon34]

Clarification:

 

* The CPU documentation is available online (of course the OKI have the documentation PDF, and I somehow found one online).

* The disassembler (the one most frequently used today) is the Lua one in the emulator repository, although I see you wrote another in Python.

* The character table is different between different versions. For example the one you use has French names.

 

... have you heard of the emulator? It *should* be easier to debug than the official emulator.

 

Reading the disassembly might be easier or harder than doing what you're tooing already, and would definitely not miss any corner cases. Or write some Ghidra integration module.

 

For the detecting pi thing, you can decompile the whole thing but the calculator is simply checking if the N such that (N/25200*pi) is equal to the provided floating point value is near a small integer enough. (it doesn't do continued fraction analysis, like (I suppose) it did in fraction detection (perhaps because it results in too many false positive)

 

The result 136273.923076923 is the best possible result for 15 BCD digits (the actual result is 136273.923076923076923... ), and that multiplied by 25200/pi is 1093108890.99973..., sufficiently close to an integer for the calculator to think that it's a precision error. (I think the 25200 thing is explained in the video, or in a comment)

Edited by anon34, 02 March 2021 - 11:57 PM.

[AlgoDump]

Thanks for the reply,

 

I have not heard of another emulator. I would certainly try it, but I cannot find it on this forum so if you can show me where to find it..

 

Reading the disassembly has some advantages, but I have found that the program structure is very layered and you quickly loose track of what it is doing.

My method of dumping the registers has the advantage that you can simply get an overview of what instructions were used, and you can simply look at the intermediate results.

Especially the BCD calculations are easy to spot since they can be read from the registers directly.

 

For instance: when you do 11^3 it solves it by multiplication, but 11^4 is solved using exp10(4*log10(11))

The algorithm for log10 in BCD is not something I could find online, and it is quite efficient. (although not as efficient as x double squared)

 

I am still trying the figure out how exactly the exponents are stored, and compared. I think it mostly uses 8 bytes + 2 bytes where one of the extra bytes indicates the exponent.

 

(* yes the character table was just taken as a quick reference)

(* most of the pi detection I have figured out, but there is more to discover still)

Edited by AlgoDump, 07 March 2021 - 11:50 AM.

[MJim]

For instance: when you do 11^3 it solves it by multiplication, but 11^4 is solved using exp10(4*log10(11))

Unfortunately I can't get my lazy brain to follow the original post of showing how the division algorithm works, but the point above may be part of the reason why complex numbers on the ES series would only work up to powers of 3.

 

I am still trying the figure out how exactly the exponents are stored, and compared. I think it mostly uses 8 bytes + 2 bytes where one of the extra bytes indicates the exponent.

I'm very interested in this too.  The value being stored as a 10 byte BCD number is what I'm guessing at myself (it's the same number of bytes used in the fx-991EX's spreasheet mode for each number).  I also found that the fx-9750GII needs ~12 bytes for each number despite being the same precision, while the ClassPad 300+ needs ~16 bytes (though it has a 3 digit exponent).

[anon34]

https://github.com/user202729/fxesplus

 

 

There's also the wiki at  http://casiocalc.wikidot.com/ which might contain some info on the number format.