42S local label caching

[Dave Britten]

From page 149 of the 42S manual, first paragraph:

"A local label search can consume a significant amount of time, depending on the length of the current program and the distance to the label. To minimize searching time, the calculator remembers the distance from the GTO or XEQ instruction to the specified local label.* This eliminates the searching time for subsequent executions of that same GTO or XEQ instruction."

And the footnote at the bottom of the page:

"*The distance to the label is stored internally as part of the GTO or XEQ instruction. If this distance is greater than 4,096 bytes in either direction (128 for short form lables [sic]; LBL 00 through LBL 14), the calculator cannot store the distance and a search must take place for each execution of the instruction."

How does this work exactly? Is that distance literally stored directly in the GTO or XEQ instruction inside the program? Or is it held elsewhere in memory? How long are these cached branching distances kept? Do they persist between multiple invocations of a program? What about if you XEQ a global label in a different program area? Will local label lookups inside that program be cached if you call that same external program multiple times inside your program?

[Sylvain Cote]

Hello Dave,

That is a lot of questions

I do not remember the details of the HP-42S implementation, but since it is a close simulation of the HP-41, here are the guidelines for the HP-41 ...

(11-11-2019 05:54 PM)Dave Britten Wrote:  Is that distance literally stored directly in the GTO or XEQ instruction inside the program?

Yep! ... for local labels only, 2 bytes GTO/XEQ for short distance LBL 00 to LBL 14 and 3 bytes GTO/XEQ for long distance for LBL 15 and up

(11-11-2019 05:54 PM)Dave Britten Wrote:  Or is it held elsewhere in memory?

Nop! ... see above

(11-11-2019 05:54 PM)Dave Britten Wrote:  How long are these cached branching distances kept?

Until the program is modified or packed, when that happens, all local GTO/XEQ distances are reset to zero

(11-11-2019 05:54 PM)Dave Britten Wrote:  Do they persist between multiple invocations of a program?

Yep!

(11-11-2019 05:54 PM)Dave Britten Wrote:  How does this work exactly?

When a GTO/XEQ is encountered and the distance field is set to zero, then the FOCAL interpreter then do a scan in search of the requested LBL, if label is found and the distance is within allowed reach then the number of bytes to jump is stored in the GTO/XEQ itself.

(11-11-2019 05:54 PM)Dave Britten Wrote:  What about if you XEQ a global label in a different program area? Will local label lookups inside that program be cached if you call that same external program multiple times inside your program?

Global GTO/XEQ are different beasts and global LBL are looked up every time.

Sylvain

Ref.: Synthetic Programming on the HP-41C, by W.C Wickes, pages 16 & 17

[Dave Britten]

That's very helpful, thanks!

(11-11-2019 06:18 PM)Sylvain Cote Wrote:  

(11-11-2019 05:54 PM)Dave Britten Wrote:  Is that distance literally stored directly in the GTO or XEQ instruction inside the program?

Yep! ... for local labels only, 2 bytes GTO/XEQ for short distance LBL 00 to LBL 14 and 3 bytes GTO/XEQ for long distance for LBL 15 and up

So GTO 10, for example, is a 2-byte instruction on my 42S. That would mean one byte encodes the GTO 10, and a second byte is reserved to store a +/-128-byte offset. And for GTO 99, which is 3 bytes, 13 bits could store +/-4,096, and the remaining 11 bits encode the GTO 99 itself. Do I have that right? XEQ instructions are always 3 bytes, so I'm not exactly sure how those are formed.

(11-11-2019 06:18 PM)Sylvain Cote Wrote:  

(11-11-2019 05:54 PM)Dave Britten Wrote:  What about if you XEQ a global label in a different program area? Will local label lookups inside that program be cached if you call that same external program multiple times inside your program?

Global GTO/XEQ are different beasts and global LBL are looked up every time.

Yeah, I know global (alpha) labels aren't cached, so I'm mostly wondering what happens if I have a program that calls XEQ "OTHER", which is part of a different program area/separated by ENDs. Will local GTO/XEQ inside "OTHER" be cached in the same way? I'm assuming yes since the offsets are stored directly in the GTO/XEQ instructions.

(11-11-2019 06:18 PM)Sylvain Cote Wrote:  Ref.: Synthetic Programming on the HP-41C, by W.C Wickes, pages 16 & 17

That's the one on the museum DVD/document set, right? I'll give it a look. I'm not going to do synthetic programming or anything like that, but I figure I can squeeze more performance out of my 42S if I understand how cached branches work, and how to avoid situations where it can't be used. Sounds like it's as simple as using LBL 00-14 only when doing short jumps, and LBL 15-99 for anything long.

And I'm assuming that the KEY...GTO/XEQ menu instructions don't do any caching, since the program pointer could be anywhere when you press the menu key. But that wouldn't have any real performance impact, since it's not like you can invoke menu keys inside a loop or something.

[Andres]

And if the distance to the label is too long, you may end up with a "Global Span" error message in the display of your 42S. I don't have the details at hand, but the maximum allowable distance was some 3500 bytes IIRC, which is quite a lot for a machine which had 8192 bytes of memory for programs and data. I suppose that those who expanded their 42S RAM from the standard 8 KBy to 32 KBy may find themselves in this situation from time to time. Once upon a time I took the effort to fill program memory space with hundreds of instructions until I was able to obtain the elusive "Global Span" message, it was not something you would find in normal usage.

[Dave Britten]

(11-11-2019 07:06 PM)Andres Wrote:  I suppose that those who expanded their 42S RAM from the standard 8 KBy to 32 KBy may find themselves in this situation from time to time.

I upgraded mine, but I can't imagine I'll ever need/want to enter a single program large enough to encounter that error. Interesting tidbit, though.

[Valentin Albillo]

.
Hi, Sylvain:

(11-11-2019 06:18 PM)Sylvain Cote Wrote:  Until the program is modified or packed, when that happens, all local GTO/XEQ distances are reset to zero

That's correct for the HP-41C family and the HP42S except that there's no packing in the latter.

Regards.
V.

[Sylvain Cote]

Dave,

(11-11-2019 06:56 PM)Dave Britten Wrote:  So GTO 10, for example, is a 2-byte instruction on my 42S. That would mean one byte encodes the GTO 10, and a second byte is reserved to store a +/-128-byte offset.

That seems to be the case for the HP-42S, as for the HP-41C the internal structures are different.
Look at The HP-41 SYNTHETIC Quick Reference Guide from Jeremy Smith, page 39 available at TOS.

(11-11-2019 06:56 PM)Dave Britten Wrote:  And for GTO 99, which is 3 bytes, 13 bits could store +/-4,096, and the remaining 11 bits encode the GTO 99 itself.
Do I have that right? XEQ instructions are always 3 bytes, so I'm not exactly sure how those are formed.

I did not have the time last night to find the HP-42S internal structure information, at this moment I am as blind as you on this subject.

(11-11-2019 06:56 PM)Dave Britten Wrote:  Will local GTO/XEQ inside "OTHER" be cached in the same way? I'm assuming yes since the offsets are stored directly in the GTO/XEQ instructions.

You are correct.

(11-11-2019 06:56 PM)Dave Britten Wrote:  

(11-11-2019 06:18 PM)Sylvain Cote Wrote:  Ref.: Synthetic Programming on the HP-41C, by W.C Wickes, pages 16 & 17

That's the one on the museum DVD/document set, right?

Yes, it is part of the Museum Document Sets (8.0) and also available at TOS.

Sylvain

[Sylvain Cote]

(11-12-2019 06:13 AM)Valentin Albillo Wrote:  

(11-11-2019 06:18 PM)Sylvain Cote Wrote:  Until the program is modified or packed, when that happens, all local GTO/XEQ distances are reset to zero

That's correct for the HP-41C family and the HP42S except that there's no packing in the latter.

Thank you Valentin for the information.

I know the HP-41C internal pretty well but my understanding of the HP-42S internal is minimal, I guess it is time to correct that deficiency.

[Sylvain Cote]

While looking for GTO/XEQ internal structure, I found these articles & web sites ...

• HP-42S Review by Brian P. Walsh, HPX Exchange v1n6 [PPC Calculator Archive]
• HP-42S Hex Table by Joseph K. Horn & Thomas B. Cadwallader, HPX Exchange v1n6 [PPC Calculator Archive]
• HP-42S Tips and Routines by Joseph K. Horn, HPX Exchange v1n6 [PPC Calculator Archive]
• HP-42S Debugger Addresses by Jeremy Smith, HPX Exchange v1n6 [PPC Calculator Archive]
• Synthetic Programming on HP-42S by Richard Nelson, EduCalc Technical Note #24 [PPC Calculator Archive]
• HP-42S Description by Craig A. Finseth [WWW]
• HP-42S Hardware Upgrade by Takayuki HOSODA [WWW]
• Long Live the HP42S by Valentin Albillo [WWW] & [PDF]
• HP-42S Emulator for Windows by Christoph Gießelink [WWW]
  

[Joe Horn]

In the "HP-42S Hex Table" article referenced above (HPX Exchange, V1 N6 P12), I wrote:

"The HP-42S uses exactly the same hex table as the HP-41 for the internal representation of user-written program functions. ... Even global labels and ENDs are the same internally. There are the same one-and two-byte LBLs, RCLs and STOs..."

One exception to code equality between the 41 and 42S was discovered by Tom Cadwallader (cf. end of above article): The 41 adds a non-packable null between sequential numbers in program memory, but the 42S adds a null after ALL numbers, not just between them. This will result in most 42S programs being slightly larger than their 41 equivalent.

[Sylvain Cote]

Hello Joe,

Local Label Searches (Users Manual P.148 & 149)
Searches for local labels occur only within the current program. To find a local label, the calculator first searches sequentially downward through the current program, starting at the location of the program pointer. If the specified label is not found before reaching the end of the program, the calculator continues the search from the beginning of the program.

A local label search can consume a significant amount of time, depending on the length of the current program and the distance to the label. To minimize searching time, the calculator remembers the distance from the GTO or XEQ instruction to the specified local label. This eliminates the searching time for subsequent executions of that same GTO or XEQ instruction.

The distance to the label is stored internally as part of the GTO or XEQ instruction. If this distance is greater than 4,096 bytes in either direction (128 bytes for short form labels; LnL 00 through LBL 14), the calculator cannot store the distance and a search must take place for each execution or the instruction.

(11-14-2019 10:54 PM)Joe Horn Wrote:  Even global labels and ENDs are the same internally. There are the same one-and two-byte LBLs, RCLs and STOs..."

Are you sure ?

For the HP-41

• the 2 bytes GTO binary format is 1011 LLLL DBBB RRRR (Label [value+1], Direction, Bytes and Registers) allowing for a maximum jump of 15 registers and 7 bytes or 112 bytes
  .
  . Ex.: GTO 00 => 1011 0001 0001 0010 => 1011 (GTO) 0001 (00) 0 (decreasing abs. address) 001 (1 byte) 0010 (2 registers) => LBL 00 is located at 15 bytes upward from the location of GTO 00
  .
• the 3 bytes GTO binary format is 1101 BBBR RRRR RRRR DLLL LLLL (Bytes, Registers, Direction and Label) allowing for a maximum jump of 511 registers and 7 bytes or 3584 bytes
  .
• the 3 bytes XEQ binary format is 1110 BBBR RRRR RRRR DLLL LLLL (Bytes, Registers, Direction and Label) allowing for a maximum jump of 511 registers and 7 bytes or 3584 bytes
  

Sylvain

[Joe Horn]

(11-15-2019 05:42 PM)Sylvain Cote Wrote:  

(11-14-2019 10:54 PM)Joe Horn Wrote:  Even global labels and ENDs are the same internally. There are the same one-and two-byte LBLs, RCLs and STOs..."

Are you sure ?

I *was* sure when I wrote it, but that was 31 years ago, soon after which my 42S was stolen and I haven't had one since. Those who own a real 42S will be able to use its built-in (unsupported) hex memory viewer/editor to explore the internal structure of GTO's, XEQ's, and LBL's.

[Sylvain Cote]

(11-15-2019 09:48 PM)Joe Horn Wrote:  I *was* sure when I wrote it, but that was 31 years ago, soon after which my 42S was stolen and I haven't had one since.

Really sorry for your loss.

(11-15-2019 09:48 PM)Joe Horn Wrote:  Those who own a real 42S will be able to use its built-in (unsupported) hex memory viewer/editor to explore the internal structure of GTO's, XEQ's, and LBL's.

ok, ok, got the hint ...

First I entered this short FOCAL (FTCAL?) program in my HP-42S

Code:

LBL "ABC"
5
LBL 00
"AAAAAAAAAAAAA"
AVIEW
TONE ST X
DSE ST X
GTO 00
END

Then I fired the debugger and scanned the memory for the AAAA's, then went to the start of the program, so here is the dump:

Code:

     0123456789ABCDEF
53DF        0C004F001
53E0 42434510010DF141
53E1 4141414141414141
53E2 4141414E7F93F793
53E3 71B61AC4090

Note: a little surprise, the nibbles are reversed within each bytes

Then I manually reversed the nibbles and reorganized things by their meaning

Code:

42S Memory Dump (reversed)    :  42S Memory Dump (rearranged)             
----------------------------  :  -----------------------------------------
0C004F00142434                :  C0 00 F4 00 41 42 43                     
5100                          :  15 00                                    
10                            :  01                                       
DF14141414141414141414141414  :  FD 41 41 41 41 41 41 41 41 41 41 41 41 41
E7                            :  7E                                       
F93F                          :  9F F3                                    
7937                          :  97 73                                    
1B61                          :  B1 16                                    
AC4090                        :  CA 04 09

Then I entered the same program in my HP-41C and with the RAMED function of the ZENROM I dumped the memory.

After that I mapped the two dump with the program code

Code:

42S Memory Dump                            :  41C Memory Dump                            :  FOCAL program   
-----------------------------------------  :  -----------------------------------------  :  ----------------
C0 00 F4 00 41 42 43                       :  C6 00 F4 00 41 42 43                       :  LBL "ABC"
15 00                                      :  15                                         :  5
01                                         :  01                                         :  LBL 00
FD 41 41 41 41 41 41 41 41 41 41 41 41 41  :  FD 41 41 41 41 41 41 41 41 41 41 41 41 41  :  "AAAAAAAAAAAAA"
7E                                         :  7E                                         :  AVIEW
9F F3                                      :  9F F3                                      :  TONE ST X
97 73                                      :  97 73                                      :  DSE ST X
B1 16                                      :  B1 93                                      :  GTO 00
CA 04 09                                   :  C4 04 09                                   :  END

There are small differences between the HP-42S and HP-41C like the global label and the end but what I was investigating here was the short form goto.

The 41C 2 bytes GTO format is 1011 LLLL DBBB RRRR and the value is B193 or 1011 0001 1001 0033 with the distance translated to 1 byte and 3 registers or 22 bytes between the GTO 00 and the LBL 00

The 42S 2 bytes GTO format is 1011 LLLL DBBB BBBB and the value is B116 or 1011 0001 1001 0110 with the distance translated to 22 bytes between the GTO 00 and the LBL 00

So the initial question about the short form goto has been answered!

Sylvain

[Werner]

I seem to remember the ENDs' and global labels' distance fields were coded the same way as in long-form GTOs.
On Emu42, I get the 'Global Span' error trying to add a single byte to a 3578-Byte Prgm containing 1789 NOT lines. I was not going to do that on my real 42S ;-) So there, at least, is no difference with the 41.

Cheers, Werner

[Sylvain Cote]

Same program as before but with a 2 bytes label and a 3 bytes goto

FOCAL program

Code:

LBL "ABC"
5
LBL 15
"AAAAAAAAAAAAA"
AVIEW
TONE ST X
DSE ST X
GTO 15
END

42S Memory dump

Code:

     0123456789ABCDEF
53DF    0C004F0014243
53E0 45100FCF0DF14141
53E1 4141414141414141
53E2 41414E7F93F79370
53E3 D61F00C5090

Reorganisation

Code:

42S Memory Dump (reversed)    :  42S Memory Dump (rearranged)
----------------------------  :  -----------------------------------------
0C004F00142434                :  C0 00 F4 00 41 42 43
5100                          :  15 00
FCF0                          :  CF 0F
DF14141414141414141414141414  :  FD 41 41 41 41 41 41 41 41 41 41 41 41 41
E7                            :  7E
F93F                          :  9F F3
7937                          :  97 73
0D61F0                        :  D0 16 0F
0C5090                        :  C0 05 09

Manual decoding

Code:

42S Memory Dump                            :  41C Memory Dump                            :  FOCAL program   
-----------------------------------------  :  -----------------------------------------  :  ----------------
C0 00 F4 00 41 42 43                       :  C6 00 F4 00 41 42 43                       :  LBL "ABC"
15 00                                      :  15                                         :  5
CF 0F                                      :  CF 0F                                      :  LBL 15
FD 41 41 41 41 41 41 41 41 41 41 41 41 41  :  FD 41 41 41 41 41 41 41 41 41 41 41 41 41  :  "AAAAAAAAAAAAA"
7E                                         :  7E                                         :  AVIEW
9F F3                                      :  9F F3                                      :  TONE ST X
97 73                                      :  97 73                                      :  DSE ST X
D0 16 0F                                   :  D2 03 8F                                   :  GTO 15
C0 05 09                                   :  C8 04 09                                   :  END

As before, there are small differences between the HP-42S and HP-41C like the global label and the end but what I am investigating here is the long form goto.

The HP-41C 3 bytes GTO format is 1101 BBBR RRRR RRRR DLLL LLLL and the value is D2038F or 1101 0010 0000 0011 1000 1111 with the distance translated to 1 byte and 3 registers or 22 bytes between the GTO 15 and the LBL 15

The HP-42S 3 bytes GTO format is 1101 BBBB BBBB BBBB DLLL LLLL and the value is D0160F or 1101 0000 0001 0110 0000 1111 with the distance translated to 22 bytes between the GTO 15 and the LBL 15

Again, the initial question about the long form goto has also been answered!

Sylvain

[Sylvain Cote]

Hello Werner,

(11-16-2019 04:50 PM)Werner Wrote:  I seem to remember the ENDs' and global labels' distance fields were coded the same way as in long-form GTOs.
On Emu42, I get the 'Global Span' error trying to add a single byte to a 3578-Byte Prgm containing 1789 NOT lines.
I was not going to do that on my real 42S ;-) So there, at least, is no difference with the 41.

If what you say is exact, EMU42 does not follow how the HP-42S is working.

As the posts above shows and as the HP-42S manuals said, on a real HP-42S, the short GTO can jump 127 bytes (2ˆ7-1) and the long GTO/XEQ can jump 4095 bytes. (2ˆ12-1).

Sylvain

[Werner]

The User Manual mentions only local labels, not global (alpha) ones. Moreover, even if the global labels also encode the distance in bytes only, the Global Span error message may be hardcoded to 3578 bytes. And emu42 uses the 42S ROM so it will be the same as a real 42S in this regard.

Cheers, Werner

[J-F Garnier]

The Global Span error is documented in the HP-42S Owner's Manual (p284):

Global Span
Attempted to insert or delete a program line that would have left
more than 3,584 bytes of program instructions between two global
labels or a global label and an END

J-F

[Joe Horn]

(11-16-2019 03:25 PM)Sylvain Cote Wrote:  ... So the initial question about the short form goto has been answered!
... Again, the initial question about the long form goto has also been answered!

Thanks, Sylvain, for your thorough exploration and explanation! It brought me back to the thrill of the old PPC days!

[Christoph Giesselink]

Almost all information was told so far. So I could only make a review from the aspect of the Emu42 RAW file import "Edit/Load Object..." when emulating a HP42S.

1) The FOCAL programs of the HP41 and the HP42S are binary compatible. The exception is Synthetic Code, the HP42S don't support synthetic programming. So Emu42 allows importing FOCAL programs saved by the V41 "File/Put User Code..." feature.

2) Joe stated correctly:

(11-14-2019 10:54 PM)Joe Horn Wrote:  One exception to code equality between the 41 and 42S was discovered by Tom Cadwallader (cf. end of above article): The 41 adds a non-packable null between sequential numbers in program memory, but the 42S adds a null after ALL numbers, not just between them. This will result in most 42S programs being slightly larger than their 41 equivalent.

This is a major problem when importing FOCAL's from V41. First of all I had to add all the null bytes after numbers on one side, on the other side the HP42S has no pack command, so it would be useful to eliminate all the nulls from the import file. This is a two pass process. In pass one I count the number of bytes required to allocate program buffer in calculator memory, therefore I don't count any null byte and only count the null bytes necessary at end of a number. Then allocate the memory and in pass two the data is copied under respect of the null bytes. Both inserting and removing of null bytes change the distance between labels.

3) Global Labels: The global labels are connected of over a global chain in one direction. So the offset to the previous global label is saved in the byte code of a global label. So at importing due the fact of inserting and removing nulls bytes I have to recalculate the global label offsets. This happens also when I add programs to the memory at end. The process includes recalculating the global label offset to get a correct link between the global labels.

4) Local Labels: I wasn't aware of local label caching and so the import function failed sometimes when loading FOCAL's from V41. This was fixed more or less recently at Emu42 v1.22. Since this version the import function overwrites the offset part of local labels with 0 bits. At the first run of the program the HP42S recalculates each offset. This I quite important doing benchmarks. Directly after importing a FOCAL program into Emu42 all local labels are not cached, so you get only repeatable results after the first run.

5) Importing FOCAL programs from Emu42 into V41: When you may have a look into the V41 sources about importing FOCALS you don't see anything about recalculation of the chain of global labels or removing the offsets in the local labels. The difference is, the import at V41 do not add or remove null bytes, so all distances are still ok after loading. To get rid of the additional null bytes at end of every number when importing from Emu42 just call the PACK command in the HP41.

6) Remark to Joe, you don't need a real HP42 and you don't need the internal memory scanner. The memory viewer inside the Debugger of Emu42 was good enough for me exploring the inner working of memory allocation inside the HP42 OS. :)