HP-33s keystroke encoding and checksums [long]



#14

It all began in an earlier thread, where those interested could follow the first steps towards reverse-engineering the encoding of HP-33s programs and the algorithm used to calculate their checksums. Now, with generous help from Paul Brogger and Derek Reyneke, I can present a (very) probable solution, or at least a solid foundation for one.

First, the checksum algorithm is, beyond doubt, a variant of CRC-16-CCITT. There seem to be doubts about the correctness of widespread implementations of this CRC (this thorough discussion suggests that HP-33s uses the "bad" variant, with a twist,) but these are beside the point; the goal is to identify the exact algorithm, not its adherence to a standard.

Second, equations are stored as ASCII strings, with a few non-ASCII code points for special symbols such as 'x' (times) and 'pi'. Decoding the full set of symbols shouldn't be difficult.

However, keystroke encodings are a bear. Each keystroke occupies three bytes, which translates to 2^24, or nearly 17 million, possible values. With a narrower checksum, collisions are guaranteed. Poring through hundreds of raw hexadecimal strings and trying to discern a coherent pattern is not easy. In the end, I had to make two key assumptions in order to move forward (and keep my sanity):

  1. The last byte of an encoding holds the additional argument (label or variable) of the command. For commands with no additional argument, the value of the last byte is zero.

  2. Successive label/variable names are encoded sequentially. With the first point in mind, all name codes must be non-zero.

... and the encodings finally started to make sense. What I have so far:

LBL A       02 B6 01    ; LBL B would be 02 B6 02, etc.
RCL A 33 C4 01 ; likewise
RTN 01 B7 00
+ 0B 31 00
x 0B 33 00
PSE 01 B4 00

Special equation symbols:

x           82
pi 87

Finally, I wrote a program to facilitate the search for further encodings. To use it, one would enter the following program into the calculator and obtain its checksum:

A0001  LBL A
A0002 <command>
A0003 RTN

(If the command accepts a label or variable name, use "A".) Then, the program is invoked as follows:

findenc "instruction name" checksum argument

where "argument" is 0 for commands without an argument, and 1 otherwise. E.g., for RCL A the invocation would be

findenc "RCL A" D85C 1

and for +

findenc "+" 9027 0

The program should print out a nicely formatted line with the instruction name and its encoding. It is written in ANSI C, and should compile and work regardless of the native host byte order and word size.

Regards,

i.

/** findenc.c */
#include <stdio.h>
#include <stdlib.h>

static unsigned short crc_table[256] = {
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7,
0x8108, 0x9129, 0xA14A, 0xB16B, 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF,
0x1231, 0x0210, 0x3273, 0x2252, 0x52B5, 0x4294, 0x72F7, 0x62D6,
0x9339, 0x8318, 0xB37B, 0xA35A, 0xD3BD, 0xC39C, 0xF3FF, 0xE3DE,
0x2462, 0x3443, 0x0420, 0x1401, 0x64E6, 0x74C7, 0x44A4, 0x5485,
0xA56A, 0xB54B, 0x8528, 0x9509, 0xE5EE, 0xF5CF, 0xC5AC, 0xD58D,
0x3653, 0x2672, 0x1611, 0x0630, 0x76D7, 0x66F6, 0x5695, 0x46B4,
0xB75B, 0xA77A, 0x9719, 0x8738, 0xF7DF, 0xE7FE, 0xD79D, 0xC7BC,
0x48C4, 0x58E5, 0x6886, 0x78A7, 0x0840, 0x1861, 0x2802, 0x3823,
0xC9CC, 0xD9ED, 0xE98E, 0xF9AF, 0x8948, 0x9969, 0xA90A, 0xB92B,
0x5AF5, 0x4AD4, 0x7AB7, 0x6A96, 0x1A71, 0x0A50, 0x3A33, 0x2A12,
0xDBFD, 0xCBDC, 0xFBBF, 0xEB9E, 0x9B79, 0x8B58, 0xBB3B, 0xAB1A,
0x6CA6, 0x7C87, 0x4CE4, 0x5CC5, 0x2C22, 0x3C03, 0x0C60, 0x1C41,
0xEDAE, 0xFD8F, 0xCDEC, 0xDDCD, 0xAD2A, 0xBD0B, 0x8D68, 0x9D49,
0x7E97, 0x6EB6, 0x5ED5, 0x4EF4, 0x3E13, 0x2E32, 0x1E51, 0x0E70,
0xFF9F, 0xEFBE, 0xDFDD, 0xCFFC, 0xBF1B, 0xAF3A, 0x9F59, 0x8F78,
0x9188, 0x81A9, 0xB1CA, 0xA1EB, 0xD10C, 0xC12D, 0xF14E, 0xE16F,
0x1080, 0x00A1, 0x30C2, 0x20E3, 0x5004, 0x4025, 0x7046, 0x6067,
0x83B9, 0x9398, 0xA3FB, 0xB3DA, 0xC33D, 0xD31C, 0xE37F, 0xF35E,
0x02B1, 0x1290, 0x22F3, 0x32D2, 0x4235, 0x5214, 0x6277, 0x7256,
0xB5EA, 0xA5CB, 0x95A8, 0x8589, 0xF56E, 0xE54F, 0xD52C, 0xC50D,
0x34E2, 0x24C3, 0x14A0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,
0xA7DB, 0xB7FA, 0x8799, 0x97B8, 0xE75F, 0xF77E, 0xC71D, 0xD73C,
0x26D3, 0x36F2, 0x0691, 0x16B0, 0x6657, 0x7676, 0x4615, 0x5634,
0xD94C, 0xC96D, 0xF90E, 0xE92F, 0x99C8, 0x89E9, 0xB98A, 0xA9AB,
0x5844, 0x4865, 0x7806, 0x6827, 0x18C0, 0x08E1, 0x3882, 0x28A3,
0xCB7D, 0xDB5C, 0xEB3F, 0xFB1E, 0x8BF9, 0x9BD8, 0xABBB, 0xBB9A,
0x4A75, 0x5A54, 0x6A37, 0x7A16, 0x0AF1, 0x1AD0, 0x2AB3, 0x3A92,
0xFD2E, 0xED0F, 0xDD6C, 0xCD4D, 0xBDAA, 0xAD8B, 0x9DE8, 0x8DC9,
0x7C26, 0x6C07, 0x5C64, 0x4C45, 0x3CA2, 0x2C83, 0x1CE0, 0x0CC1,
0xEF1F, 0xFF3E, 0xCF5D, 0xDF7C, 0xAF9B, 0xBFBA, 0x8FD9, 0x9FF8,
0x6E17, 0x7E36, 0x4E55, 0x5E74, 0x2E93, 0x3EB2, 0x0ED1, 0x1EF0
};

unsigned short
crc_ccitt(unsigned char *buf, unsigned len) {
unsigned short crc = 0;

    while (len--)
crc = (crc << 8) ^ crc_table[(crc >> 8) ^ *buf++];
return crc;
}

int
main(int argc, char *argv[])
{
long i;
unsigned char ibuf[9];
unsigned short crc;
char *iname;
int arg;

    /* instruction name, CRC, argument */
if (argc < 4) {
fprintf(stderr, "Usage: findenc <insn-name> <crc> <arg>\n");
return 1;
}

    /* extract and prepare arguments */
iname = argv[1];
crc = (unsigned short) strtoul(argv[2], (char **) NULL, 16);
arg = *argv[3] == '1';

    /* buffer setup */
ibuf[0] = 0x02;
ibuf[1] = 0xB6;
ibuf[2] = 0x01;
ibuf[5] = arg;
ibuf[6] = 0x01;
ibuf[7] = 0xB7;
ibuf[8] = 0x00;

    for (i = 0; i < 65536; i++) {       /* 2^16 */
ibuf[3] = i >> 8;
ibuf[4] = i & 0xFF;
if (crc_ccitt(ibuf, 9) == crc)
printf("%-16s%02X %02X %02X\n", iname, i >> 8, i & 0xFF, arg);
}
return 0;
}


Edited: 16 June 2006, 3:12 a.m.


#15

Bravo - Let it never be said that calculator programmers don't know about programming! Just an addendum here, all of this would never have been necessary if HP in their wisdom had not decided on the silly 26 label limitation in the 33S (sorry - a pet gripe, had to get it off my chest)

Derek


#16

The 33s calculator is a direct development from the 32sii, which nobody ever complained about WRT labels, as its memory was very small. Now that the memory is improved, there is all this griping about labels.

Sheesh! :-)

Edited: 16 June 2006, 7:57 a.m.


#17

Quote:
The 33s calculator is a direct development from the 32sii, which nobody ever complained about WRT labels, as its memory was very small.

Speaking of 32sii, is it known how much RAM did it have? Not user memory -- I know it was 384 bytes -- but total system RAM. Also, what was its processor speed (in MHz)?

Regards,

i.


#18

Quote:
Speaking of 32sii, is it known how much RAM did it have? Not user memory -- I know it was 384 bytes -- but total system RAM. Also, what was its processor speed (in MHz)?

  • 16 KB ROM
  • 512 bytes RAM (128 + 384)
  • 1LR3 Sacajawea @ 640KHz

The 1LR3 is quite similar to the 1LR2 Lewis chip and belongs to the lastest chips of the Saturn family (like 1LT8 Clarke or Yorke in the HP48 family). In difference to the higher Pioneer calculators (17BII, HP42S, ...) the internal firmware is complete written in assembler, there's no RPL interpreter inside.

Christoph


#19

Quote:
1LR3 Sacajawea @ 640KHz (on the 32SII)

The 1LR3 is quite similar to the 1LR2 Lewis chip and belongs to the lastest chips of the Saturn family (like 1LT8 Clarke or Yorke in the HP48 family).


Thank you for the technical info, Christoph. I believe that the high-end Pioneers (17B/BII, 27S, 42S) used a 1-MHz Saturn CPU.

These chips were obviously named for the Lewis and Clark expedition of 1803-1806, which has received considerable attention in the US the past few years, in celebration of its bicentennial of reaching the Pacific Ocean. Captain Meriwether Lewis and Lieutenant William Clark were the leaders; York was a slave (albeit valued) on the team; Sacajawea was an "American Indian" (North American indigenous people) who guided portions of the expedition, and since 2000 has been featured on the US $1 coin.

So, there's some historical background to HP's theme, noting the correct American spellings of "Clark" and "York".

Regards,

-- KS


Edited: 18 June 2006, 5:09 p.m.


#20

I just read that reacent book on Lewis and Clark....and of course hte spellings that both those men used are rather more fluid and phonetci than our rigid froze n spelling of today.

Of interest is the spelling of that remarkable teenage mother, who travelled across the west, with an *infant* son, her French husband, and a remarkable band of officers and men. (See my spelling in the subject line).


#21

Quote:
and of course hte spellings that both those men used are rather more fluid and phonetci than our rigid froze n spelling of today.

Bill, it seems that some of your spellings don't follow rigid rules! ;-)

BTW, The Curator has re-instated editing and deletion after response.


Also, I'd agree that "Sacagawea" is today's accepted spelling, although "Sacajawea" has been used to name many things in honor over the years.

-- KS


#22

:-D

#23

I recall reading somewhere that brave young lady's name
was spelled 19 different ways in the diary made by [LewisClark].

Which only made it more difficult to determine the proper
pronoun-ski-ation, meaning and spelling.

Ren
dona nobis pacem

#24

For those who don't know anything about the Lewis and Clark expedition you may have a look here http://en.wikipedia.org/wiki/Lewis_and_Clark_Expedition.

Cheers

Christoph

#25

Quote:
  • 16 KB ROM
  • 512 bytes RAM (128 + 384)
  • 1LR3 Sacajawea @ 640KHz

Thanks. I've been wondering whether the SPLB31A (the core of 33s) could have been programmed to emulate the 32sii's Saturn and have enough RAM left to cover the calculator's memory requirements. Well guess what... SPLB31A has 4 KB plus 192 bytes dedicated zero page memory. Subtract page 1 (256 bytes) for the 6502's stack and another page for the emulator scratch memory (which is quite generous), and you're left with a 3456 byte user area, exactly nine times larger than 32sii.

So why didn't HP take that route? Who knows...

(As an aside, I recently browsed a few semiconductor manufacturers' sites to see what sizes of low-power SRAM are available. 256 Kbit (32 KB) is the lowest available offering, and it seems that Samsung is discontinuing that size later this year. In that light, the decision to go with 32 KB three years ago makes a lot of sense.)

Regards,

i.


#26

Because it would have been slower than molasses flowing uphill in the middle of winter. The Sunplus chip is a slow part to begin with, and burdening it with Saturn emulation would result in a ridiculously slow calculator.

I've done plenty of 6502 programming, and know many of the tricks to wring performance out of it, but you can only do so much.


Possibly Related Threads...
Thread Author Replies Views Last Post
  HP Prime: Long integers (continued) Helge Gabert 2 366 11-07-2013, 11:24 AM
Last Post: Helge Gabert
  HP Prime: Pass "Long" Integers to a Program Helge Gabert 6 655 11-03-2013, 01:12 PM
Last Post: Helge Gabert
  HP Prime polynomial long division bluesun08 13 981 10-30-2013, 03:29 AM
Last Post: parisse
  A very long HP-17BII equation Gerson W. Barbosa 22 1,480 04-19-2013, 12:37 AM
Last Post: Gerson W. Barbosa
  A long WP-34S night Siegfried (Austria) 10 829 04-16-2013, 02:11 AM
Last Post: Siegfried (Austria)
  HP-25 left on for a long, long, while Matt Agajanian 12 840 04-10-2013, 11:33 PM
Last Post: Steve Leibson
  RPL long vs. short names peacecalc 5 484 10-30-2012, 01:25 PM
Last Post: peacecalc
  HP41 Long term storage Steve Hunt 6 498 09-27-2012, 11:08 PM
Last Post: db (martinez, ca.)
  33s/35s Checksums paradigm Matt Agajanian 25 1,328 03-03-2012, 08:55 PM
Last Post: Matt Agajanian
  Most usable keystroke calculator? Sid Cave 32 1,775 01-07-2012, 03:49 PM
Last Post: Lutz Jacob

Forum Jump: