(Comp.sys.handhelds)
Item: 1997 by seroussi at hplabsb.HP.COM
Author: [Gadiel Seroussi]
  Subj: HP48 compact arrays
  Date: Fri Feb 08 1991

The COMPACT directory uses HP48 linked arrays to implement "compact arrays"
of positive integers.  These arrays allow you to store large tables of
positive binary integers using significantly less storage than would be
required with either real arrays or lists of binaries, with an access time
comparable to that of real arrays (much faster than lists of binaries).

A compact array shows on the stack as "Linked Array", and cannot be edited
directly (conversion routines are provided).

The internal structure of a compact array is as follows:

<02a0a> - header (5 nib)
<size>  - size of object excluding header (5 nib)
<isize> - size of array elements, in nibbles (5 nib)
<n>     - number of elements (5 nib)
<element 1> <element 2> ..... <element n>  (<isize> nibbles each).

Other headers could have been chosen but "linked array" was unused enough
to justify the choice (and choices like "code" or "string" would be
confusing).

The following variables are included:

IGETB: retrieve an element of the array, as a binary number.

        2: A (compact array)
        1: k (Real)          ----> 1: A(k)  (binary)

IGET: retrieve an element of the array, as a real number.

        2: A (compact array)
        1: k (Real)          ----> 1: A(k)  (Real).

        If k <= 0, the number of elements of the array is returned.
        Subscript range is checked.

IPUT: store a value in the array.

        3: A (compact array)
        2: k (Real)
        1: x (Real or binary)  ----> 1: A (compact array, with A(k)=x).

        Subscript range is checked, k <= 0 is not allowed. The value x is
        truncated to the size of the array elements.

ICON: generate a compact array with constant elements.

        3: n (Real)
        2: isize (Real)
        1: c (Real or binary)  ----> 1: A (compact array).

        A has n elements, isize nibbles each, all set to the value c. While
        it is legal to set isize > 16, the access routines will only handle
        up to 16 nibble values.

ISIZE: find out the value of <isize>.

        1: A (compact array)   ----> 1: isize (Real)

ITOA: Convert compact array to real array.

        1: A (compact array)   ----> 1: RA (Array of Real).

ITOB: Convert compact array to list of binaries.

        1: A (compact array)   ----> 1: BL (List of Binary).

ATOI: Convert real array to compact array.

        2: RA (Array of Real)
        1: isize (real)        ----> 1: A (compact array)

BTOI: Convert list of binaries to compact array.

        2: BL (List of Binary)
        1: isize (real)        ----> 1: A (compact array)

        For both ATOI and BTOI, if isize == 0, the least number of nibbles
        will be used that can accommodate the largest value in RA or BL
        (resp.).

BMAX: Find the largest value in a list of binaries (aux. function).

p.small: an example of a compact array. A list of the first 1000 prime
numbers. It takes 2010 bytes of storage, compared to 8012.5 bytes for a
real array, or around 7000 bytes for a "well packed" list of binaries
(which ITOB will NOT produce).

Other remarks:
1. The conversion routines are written in user language. Since I consider
   them "one-time" events, no special effort was made to make them faster.
2. All access routines are affected by the current setting of the binary
   word size (set word size >= isize for things to work properly).

This package was developed for a Version D ROM. It may or may not work on
yours. It may or may not destroy your data and/or your calculator. Use it
at your own risk. No warranties of any kind.

Enjoy,

Gadiel Seroussi
HP Labs (but no relation to Corvallis)

----------
  Resp: 1 of 1 by jurjen at cwi.nl
Author: [Jurjen NE Bos]
  Date: Fri Feb 08 1991 19:15

This program (for storing arrays of integers in a compact form) uses linked
arrays as the data type of choice.  The author says:

        Other headers could have been chosen but "linked array" was
        unused > enough to justify the choice (and choices like
        "code" or "string" would > be confusing).

How do we know for sure that the HP48 ROM does not make any assumptions
about the contents of a Linked Array?  The name suggests that the contents
may have a structure that contains addresses of other objects.

Are you sure the garbage collector allows one to make Linked Array with
anything in it?

For that matter, does anybody know what a Linked Array actually does?  I
know there is one in the ROM (sorry, I don't know the address), but it
wasn't clear to me what it did.  It did contain machine code, I recall.
Until we understand them, I don't consider it a safe idea to use Linked
Arrays as objects in a program.