HP33S Check digit



#2

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


#3

I can't help you with your question, but . . .

. . . can we hear the "long story"? (Just curious.)


#4

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


#5

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.


#6

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.

#7

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


#8

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

#9

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

  1. 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.

  2. 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


#10

An answer worthy of a master, why didn't I think of that?


#11

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.

#12

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


#13

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:

  1. First byte: shift state (none, left, right).

  2. Second byte: key code.

  3. 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.


#14

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.


#15

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.


#16

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


#17

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.


#18

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.

#19

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.


#20

Results so far:

  1. 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.

  2. Checking for RTN with the tentative encodings for LBL A produces 256 possible values.

  3. 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.


Possibly Related Threads...
Thread Author Replies Views Last Post
  Prime Version Check Thomas Chrapkiewicz 1 367 10-21-2013, 10:12 AM
Last Post: Han
  How to check / repair a HP 82106A module for HP41C calculator ? Eduardo Mingo 13 1,232 01-07-2013, 11:05 AM
Last Post: Diego Diaz
  Check on mathematical identity Namir 21 1,632 08-26-2012, 11:21 AM
Last Post: Les Koller
  [WP 34S] Final documentation check Walter B 18 1,540 07-06-2012, 02:10 AM
Last Post: Walter B
  HP-32E missing digit Matt Agajanian 11 1,061 03-21-2012, 11:08 PM
Last Post: Luiz C. Vieira (Brazil)
  41CX-MCODE: Digit Sum function Ángel Martin 17 1,485 12-09-2011, 08:06 AM
Last Post: Ángel Martin
  The most abused phrase "Check Back Soon" Michael de Estrada 8 862 10-11-2011, 10:25 PM
Last Post: hpnut
  [edited] from the HHC email list, what is the proper answer to 8 ENTER 3 divide 2 divide on 10 digit calc Gene Wright 10 981 10-02-2011, 01:07 PM
Last Post: Dieter
  41-MCODE: Updated AECROM w/ 13-digit Math Ángel Martin 8 831 06-04-2011, 02:55 AM
Last Post: Ángel Martin
  Do the Ebay sellers check the merchandise? Gonzalo Fernandez 35 2,672 02-05-2011, 01:21 PM
Last Post: Michael de Estrada

Forum Jump: