[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: Maximum Array Sizes in 16 bit C

[Aron Insinga]

FWIW, I just saw this in code generated by bison:

     (yyvsp[-4].string_val), (yyvsp[-2].string_val), (yyvsp[0].string_val)

(IIUC) referencing the addresses under the top of the stack when passing 
$2, $4, $6 into a function from an action (skipping a couple of 
tokens).  So the sign just depends on which way the stack is growing.

As for range checking of pointers into a malloc'd block of memory, the 
pointer could have just 2 things: the address at the start of the block 
and the pointer itself, some moving address in the block; and then 
before the start of the block malloc could stash the address of the end 
of the block (where it could be referenced by all pointers into the 
block).  So instead of a triple word, the pointer is a double word, and 
the malloc'd block has an extra word before it.  This must have been 
done before by someone, somewhere.

I don't think of pointers and arrays in C as the same thing, but rather 
array references as an alternate syntax for pointer arithmetic (or vice 
versa).

- Aron