▼
Posts: 23
Threads: 8
Joined: Sep 2011
Hi all,
Can someone possibly tell me how the label check digits on a 33S are calculated? (shift left -> mem -> 2 ->shift right -> show). It's a long story but basically, I need to duplicate the process programmatically.
Thanks
Derek
▼
Posts: 1,153
Threads: 94
Joined: Mar 2006
I can't help you with your question, but . . .
. . . can we hear the "long story"? (Just curious.)
▼
Posts: 23
Threads: 8
Joined: Sep 2011
OK. I have written a series of survey routines for the 33S, but with the limitation of 26 labels - can only load some of them at any one time. In order to provide options for the people who buy this suite, I have then written a VB program that allocates labels, keeps track of them and provides a listing of each program. For completeness, it would be nice to include the check digit with the listing to enable users to check that they have keyed-in correctly. Make sense?
Derek
▼
Posts: 1,153
Threads: 94
Joined: Mar 2006
Very much so. If you key in the programs yourself (to test them?), won't you then have access to each program's checksum?
If you're planning to reassign the programs to different labels, as necessary, I can see that then you'd want a way to algorithmically predict the checksums.
▼
Posts: 23
Threads: 8
Joined: Sep 2011
That's pretty much it, actual label assignment would be totally at the mercy of the user - depending on which routines he decided to load.
Posts: 1,792
Threads: 62
Joined: Jan 2005
Derek --
These are "checksums", which are generated from the contents of entire program blocks (from LBL through line before next LBL or the end of program memory) as well as from equations. Checksums provide a means of verification that a known program or equation was entered correctly. The four hexadecimal digits yield 65,536 possible values; minor differences in the code generally produce major differences in the checksum, which improves the likelihood that a small error in entry of the program or equation will be noticed.
The HP-32S, HP-32SII, and HP-33S offer the checksum function. (Regrettably, the HP-42S does not, and it would be most useful, with capacity for long programs but no I/O).
For a given program or equation, the three calculators listed above will produce different checksums.
There's probably some useful information in Wikipedia or other source about general philosophy and methods to calculate checksums. As for the specific method used in the HP-33S, I really couldn't say...
-- KS
▼
Posts: 23
Threads: 8
Joined: Sep 2011
Thanks Karl,
I'll keep delving into it. I'm sure that somewhere there must be a step-by-step methodology that would tell me exactly how to evaluate an expression into a hex value.
Derek
Posts: 33
Threads: 5
Joined: May 2006
Quote:
Can someone possibly tell me how the label check digits on a 33S are calculated? (shift left -> mem -> 2 ->shift right -> show). It's a long story but basically, I need to duplicate the process programmatically.
Ah, that's one of the reasons I wanted to get a 33S myself (another long story.) I don't have a ready answer to your question, but I do have an idea how to identify the checksum algorithm, if it is a common one. I believe it is, because
- By all accounts, development of the 33S firmware was a bit of a rush job, as witnessed by the number of initial bugs, complete disregard for memory efficiency and the (relatively) short time frame.
- That being the case, I seriously doubt that any significant time was spent on analyzing the frequency and type of program entry errors and finding some funky CRC polynomial that would minimize checksum collisions.
Therefore, I am reasonably certain that the chosen algorithm was something well known and widely available, such as CRC-32 or Adler-32. These are 32-bit checksums, so probably the upper 16 bits of the result are discarded or exclusive-ORed with the lower 16 bits.
So, how to find out? Depends on what is the shortest program you can write and get the checksum for. Let's assume it is a label alone, e.g.,
A0001 LBL A
You know it is three bytes long, and you know the checksum. You don't know the byte values, nor the algorithm. Suppose that the algorithm is CRC-32, and check all 2^(3*8) values to see which ones produce the known checksum. You will get a number of collisions, so try to find a value which makes sense for the label step.
Once you have this tentative value, extend the program by a single instruction, say RTN, and repeat the process. Try another algorithm if the assumed one gives nonsensical results, etc. Mapping the entire instruction set (and constants, and in-program equations) is likely to be gruelling work, but I believe it could be done.
Regards,
I. Nejgebauer
▼
Posts: 23
Threads: 8
Joined: Sep 2011
An answer worthy of a master, why didn't I think of that?
▼
Posts: 1,788
Threads: 36
Joined: Aug 2007
The checksum could be over the ASCII value of the input or over some internal representation of it. Also, the first thing I would check is a simple arithmetic sum and its complement.
Posts: 1,153
Threads: 94
Joined: Mar 2006
Or, you could compare the checksum for "LBL A" to that for "LBL B" and then for "LBL C" -- knowing that the only thing changing is the code for the label itself (not the "LBL" command code).
Another start: short EQNs. Here are a few:
A -- 58E5
B -- 6886
C -- 78A7
D -- 0840
E -- 1861
Looks like a nifty puzzle, eh?
I would assume, given the rushed development, that the checksum algorithm (if not the actual resulting values) is the same as that for the 32S and 32SII. That could be easily checked -- by comparing results like those above with those obtained on each of the other models. (The internal coding of EQNs or commands like "LBL", for example, may be different; but a similar algorithm would probably result in similar patterns in what may be otherwise differing results.)
▼
Posts: 33
Threads: 5
Joined: May 2006
Quote:
Or, you could compare the checksum for "LBL A" to that for "LBL B" and then for "LBL C" -- knowing that the only thing changing is the code for the label itself (not the "LBL" command code).
Yes, that would be helpful for quickly checking the assumptions about the algorithm and the encoded values. Could you post the checksums for the following six short programs?
One:
A0001 LBL A
Two:
A0001 LBL A
A0002 RTN
Three:
A0001 LBL A
A0002 RTN
A0003 RTN
Four:
B0001 LBL B
Five:
B0001 LBL B
B0002 RTN
Six:
B0001 LBL B
B0002 RTN
B0003 RTN
Any two consecutive labels are fine if A or B are already used on your machine.
I tried thinking like a programmer faced with an impossible schedule (is there any other sort? ;) and suppressing my usual optimizing instincts, trying to come up with a plausible three-byte instruction encoding. A possibility:
- First byte: shift state (none, left, right).
- Second byte: key code.
- Third byte: additional argument, if any.
That's terribly wasteful, but also very simple and straightforward. Such a scheme, if it's actually used, would speed up the reverse-engineering job we're discussing quite a bit.
Regards,
i.
▼
Posts: 1,153
Threads: 94
Joined: Mar 2006
Quote:
. . . Could you post the checksums for the following six short programs?
One:
A0001 LBL A -- LN=3 CK=CAEA
Two:
A0001 LBL A -- LN=6 CK=AEE5
A0002 RTN
Three:
A0001 LBL A -- LN=9 CK=F970
A0002 RTN
A0003 RTN
Four:
B0001 LBL B -- LN=3 CK=FA89
Five:
B0001 LBL B -- LN=6 CK=3539
B0002 RTN
Six:
B0001 LBL B -- LN=9 CK=21F2
B0002 RTN
B0003 RTN
(Someone may wish to double-check my transcriptions.)
Edited: 9 June 2006, 5:50 p.m.
▼
Posts: 33
Threads: 5
Joined: May 2006
Thanks for the checksums. I think I have found the algorithm -- it's CRC-16-CCITT (polynomial 0x1021) with the initial value of zero (the standard calls for 0xFFFF) and no final complement. Short equation checksums you have posted earlier proved to be extremely useful; good thinking!
I tried to decode the short programs (LBL x), assuming that the difference in encoding LBL A and LBL B will be in the final byte, but I get too many collisions to make any useful conclusion. So, could you please post the checksums for another two programs?
One:
C0001 LBL C
Two:
D0001 LBL D
Regards,
i.
▼
Posts: 1,153
Threads: 94
Joined: Mar 2006
Quote:
. . . So, could you please post the checksums for another two programs?
One:
C0001 LBL C -- EAA8
Two:
D0001 LBL D -- 9A4F
Sounds as if you're making progress. Thanks!
-- pb
▼
Posts: 33
Threads: 5
Joined: May 2006
Quote:
Sounds as if you're making progress. Thanks!
I'm still getting a huge number of collisions (small wonder -- squishing 2^24 possible values into 2^16 is bound to give 2^8 collisions, assuming uniform distribution), but there are a couple of encodings that look promising. I could use the checksums for a few more simple programs (see below) -- I sincerely hope I am not pestering you too much!
To Derek, who has started this thread: are you still with us? Are you working on the decoding? With the information I have already posted and the calculator in your hands, you could make quick progress. Keep us posted.
I'm making arrangements to get my own 33s, which should take a couple of weeks. Once I have it, I will try to do the complete decoding.
Now, the programs.
One:
S0001 LBL S
Two:
V0001 LBL V
Three:
A0001 LBL A
A0002 +
A0003 RTN
Four:
A0001 LBL A
A0002 x
A0003 RTN
Five:
A0001 LBL A
A0002 PSE
A0003 RTN
Regrads,
i.
▼
Posts: 23
Threads: 8
Joined: Sep 2011
Not half as much progress as you are by the looks of it, trying to turn the above into workable VB code is proving to be a nightmare. Seriously considering writing the checksum routine in C and then trying to hook into it somehow.
Posts: 1,153
Threads: 94
Joined: Mar 2006
Quote:
. . . I could use the checksums for a few more simple programs . . .
One:
S0001 LBL S -- LN=3; CK=F899
Two:
V0001 LBL V -- LN=3; CK=A83C
Three:
A0001 LBL A -- LN=9; CK=9027
A0002 +
A0003 RTN
Four:
A0001 LBL A -- LN=9; CK=D4A4
A0002 x
A0003 RTN
Five:
A0001 LBL A -- LN=9; CK=17A2
A0002 PSE
A0003 RTN
In case it helps to have a couple more EQNs:
EQN A+ -- LN=2; CK=ABF4
EQN Ax -- LN=2; CK=8F37
-- pb
Edited: 13 June 2006, 9:48 a.m.
▼
Posts: 33
Threads: 5
Joined: May 2006
Results so far:
- I have 16 possible encodings for LBL A, found by assuming that the encodings for successive labels would differ in the last byte, and be encoded sequentially.
- Checking for RTN with the tentative encodings for LBL A produces 256 possible values.
- Analysis of these values shows that the middle byte is not a simple key code; no pairs of possible encodings have the same middle byte.
It's possible that shift states are lumped together with the key code, or that the first two bytes are the ROM entry point for the corresponding function, or something even more weird; I really can't tell.
I contacted Derek by mail, and I expect to receive some additional checksums tomorrow. I will post the results as soon as I find something that makes sense.
Quote:
In case it helps to have a couple more EQNs:
Equations are ASCII-encoded strings with some non-ASCII codes for special characters; they should be relatively easy to map out. Keystroke encodings are the difficult case. Anyway, thanks a lot for the patience and support!
Regards,
i.
|