HP33S Check digit

[Derek]

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

[Paul Brogger]

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

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

[Derek]

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

[Paul Brogger]

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.

[Derek]

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.

[Karl Schneider]

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

[Derek]

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

[Ivan Nejgebauer]

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

[Derek]

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

[David Smith]

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.

[Paul Brogger]

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

[Ivan Nejgebauer]

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.

[Paul Brogger]

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.

[Ivan Nejgebauer]

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.

[Paul Brogger]

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

[Ivan Nejgebauer]

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.

[Derek]

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.

[Paul Brogger]

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.

[Ivan Nejgebauer]

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.