[COFF] Re: [TUHS] Maximum Array Sizes in 16 bit C

[COFF] Re: [TUHS] Maximum Array Sizes in 16 bit C

[Douglas McIlroy]

[-- Attachment #1: Type: text/plain, Size: 1570 bytes --]

Moved to Coff, because it's about programming style, not history.

> Perhaps I'm missing something? Clever arithmetic in the index
> calculation aside, this is semantically different than using an actual
> negative integer to index into an array? Moreover, if the intent is to
> start the sequence with 0, why set `fib(0)` to 1? How is this
> substantially different from the usual way of writing this:

I said the Fibonacci example was silly. Maybe you'll be more convinced by
the binomial-coefficient program below.

The array of interest is fib. base is simply scaffolding and doesn't appear
in the working code. You won't find the ith Fibonacci in base[i]; it's in
fib(i). But fib(-1) exists. What's important is that the C convention of
array indexes beginning at 0 has been circumvented.

I could be accused of subterfuge in depending on the semantics of static
storage to initialize fib(-1) to zero. Subterfuge or not, it's customary C
usage. The binomial-coefficient program relies on "out-of-bounds" zeros
abutting two sides of a triangle.

int base[N][N+2];
#define binom(n,i) base[n][(i)+1]

void fill() {
    binom(0,0) = 1;
    for(n=1; n<N; n++)
for(i=0; i<=n; i++)
            binom(n,i) = binom(n-1,i) + binom(n,i-1);
}

I think the offset algorithm above looks better than the more typical one
below.
The two programs happen to have identical character counts.

int binom[N][N+1];

void fill() {
    for(n=0; n<N; n++) {
        binom[n][0] = 1;
for(i=1; i<n; i++)
            binom[n][i] = binom[n-1][i] + binom[n][i-1];
binom[n][n] = 1;
    }
}

Doug

[-- Attachment #2: Type: text/html, Size: 2376 bytes --]

[COFF] Re: Maximum Array Sizes in 16 bit C

[Ralph Corderoy]

Hi Doug,

> int base[N][N+2];
> #define binom(n,i) base[n][(i)+1]

Thanks for the interesting prompt.  I've been having a think about it
along the lines of sliding the ints in memory.

Have you considered having a single dimension of ints and then accessing
them as if a two-dimensional array, with [0][0] being offset?

    $ cat offset.c
    #include <stdio.h>

    #define N 4  // N×N values
    #define L 3  // L columns of 0 to the left
    #define U 2  // U columns of 0 upwards

    int main()
    {
        char m[(U + N) * (L + N)] =
            "abcdefg"
            "hijklmn"
            "opq+BCD"  // The '+' is a[0][0].
            "rstEFGH"
            "uvwIJKL"
            "xyzMNOP";
        char (*a)[L + N] = (char (*)[L + N])&m[U * (L + N) + L];

        for (int y = -U; y < N; y++) {
            if (!y)
                putchar('\n');

            for (int x = -L; x < N; x++) {
                if (!x)
                    putchar(' ');

                putchar(a[y][x]);  // y,x relative to ‘+’
            }
            putchar('\n');
        }
    }
    $ gcc -Wall -Wextra -Werror offset.c
    $ ./a.out
    abc defg
    hij klmn

    opq +BCD
    rst EFGH
    uvw IJKL
    xyz MNOP
    $

-- 
Cheers, Ralph.

[COFF] Re: [TUHS] Maximum Array Sizes in 16 bit C

[Dan Cross]

On Fri, Sep 20, 2024 at 8:22 PM Douglas McIlroy
<douglas.mcilroy@dartmouth.edu> wrote:
> Moved to Coff, because it's about programming style, not history.

Heh, I had deliberately removed the list in my response to you, but
it's not too embarrassing to have this redirected back to COFF. :-)

> > Perhaps I'm missing something? Clever arithmetic in the index
> > calculation aside, this is semantically different than using an actual
> > negative integer to index into an array? Moreover, if the intent is to
> > start the sequence with 0, why set `fib(0)` to 1? How is this
> > substantially different from the usual way of writing this:
>
> I said the Fibonacci example was silly. Maybe you'll be more convinced by the binomial-coefficient program below.
> [snip]

The caveat sent later notwithstanding, I agree that I was overly
fixated on the Fibonacci example in my response and this better
illustrates the motivation for the technique.

Regardless, I feel like we're somewhat speaking at cross-purposes. In
particular, this uses macros to introduce a more pleasant syntax, but
at the language level, the index into the underlying array is always
non-negative and within the array's defined bounds. This is
qualitatively and quantitatively different from using an actual
negative value in the actual indexing operation.

        - Dan C.

[COFF] Re: [TUHS] Maximum Array Sizes in 16 bit C

[Douglas McIlroy]

[-- Attachment #1: Type: text/plain, Size: 494 bytes --]

A summary of a couple of longer posts.

Ralph Corderoy and I used different C syntax than to access an MxN array A,
whose subscripts begin at M0 and N0 in the respective dimensions. Here's a
somewhat simplified version of both. In our examples, M0 and M0 were
negative.

Mine:
int base[M][N];
#define A(i,j) base[i-M0][j-N0]

Ralph's
int base[M][N];
int (*A)[N] = (int(*)[N])&base[-M0][-N0];

In my scheme element references must be written A(i,j). Ralph retains C
array syntax, A[i][j].

Doug

[-- Attachment #2: Type: text/html, Size: 755 bytes --]

[COFF] Re: [TUHS] Maximum Array Sizes in 16 bit C

[Douglas McIlroy]

[-- Attachment #1: Type: text/plain, Size: 366 bytes --]

Mea culpa.

I thought I could offer a simple example, but my binomial-coefficient
program is wrong, and loses its force when corrected. For a convincing
example, see the program in
    https://digitalcommons.dartmouth.edu/cs_tr/385/
Unfortunately you have to read a couple of pages of explanation to see what
this program is up to. It's a fun problem, though.

Doug

[-- Attachment #2: Type: text/html, Size: 578 bytes --]