Contiguous Arrays

[Gordon Burditt]

> > UNPORTABILITY ALERT!
> > There is no guarantee that there is a way to represent &space[0] - 101
> > at all.  Further, computing it may cause overflows such that
> > 
> > 	(&space[0] - 101) + 101 != &space[0]
>Please explain?  What machine does this, or what architecture would allow
>the machine or programming language to do it?

Ok, I'm going to use the Intel 80386 as an example.  There are lots of
combinations of memory models and processor modes to consider.
It is perhaps possible to make unportable code that creates pointers that
run off the end of arrays like this "work right" but it comes at a very 
large cost in code size and execution time.

Problem 1:  in protected mode, loading a bad segment number (putting a bad
pointer into a register) causes traps.
Problem 2:  in non-protected mode, the pointer math necessary to 
handle both out-of-range pointers and arrays > 64k is very expensive.
It is possible to blow it in a way that works on an 8086 and fails on an 80386.

> > It could happen that (&space[0] - 101) == (int *) NULL.  Even computing
> > &space[0] - 101 could cause core dumps (MSDOS equivalent:  hang system
> > forcing use of RESET, optionally trashing FAT on hard disk)
>
>This is not necessarily a condemnation of any computer that shows such lack
>of concern for basic mathematics, but I would expect a computer that does
>anything but return equality in the above expression to be broken as a

*POINTER* arithmetic is not basic mathematics.  Segmented architectures
usually have a segment number, which is ordinarily a "magic token" that
you don't do math on, and an offset, which you can do math on.  How (and
whether) you handle carries from the offset to the segment depends on
the memory model.  There isn't usually an "increment pointer" instruction.

* * * WARNING * * * READING FURTHER MAY INDUCE VOMITING * * * WARNING * * *

Consider the 80386 protected mode (with 16-bit addressing).  A segment 
register (16 bits) contains an index (segment number), a table indicator 
(global or local), and a privilege level.  A memory access requires a
16-bit offset, computed from fields of the instruction and various registers,
depending on the address mode, and a reference to one of 6 segment registers.
The machine instructions don't provide a carry from the offset part to the
segment.

When you load a segment register, information is loaded from the descriptor
tables on the origin, length, and privileges of the segment.  If the 
segment isn't valid, you get one of several types of traps.  NO ACCESS 
NEED BE ATTEMPTED - JUST LOADING A BAD SEGMENT NUMBER INTO A SEGMENT
REGISTER CAUSES A TRAP.  (A NULL pointer is a special case:  you can load it,
but it traps if you try to dereference it).  Why do it this way?  It saves
a substantial amount of time doing this when the segment register is loaded 
instead of fetching and checking this information on every access.

Small model:  pointers are 16 bits, and pointer math works fine. 64k data max.
Large model:  pointers are 32 bits, and pointer math works fine, with no
carries into the segment number.  No object (including whole arrays) may 
exceed 64k.
Huge model:  pointers are 32 bits.  Pointer math must propogate carries
into the segment number.  (To further complicate things, carries have to
propogate into the segment number field, which does NOT start in the low-order
bit of the segment register).  Huge arrays must have consecutive segment 
numbers.  

Now, what happens if you want to compute &foo[-256] (foo is an int array)?  
foo starts at 88:0x0000.  (Note:  NULL is 0:0x0000, and pointer comparisons
(OUGHT TO) compare 32 bits)  So &foo[-256] is 87:0xFE00.  As it happens, 
there is no segment 87 allocated.  If you put &foo[-256] into a register 
(pair), you get a General Protection Trap.  NO ACCESS NEED BE ATTEMPTED.

Consider the 80386 protected mode (with 32-bit addressing).  This is
the same as 16-bit addressing, except the offset can be much bigger, and
each pointer gets 16 bits larger.  One segment can be so big nobody would 
ever need more than one, right? Wasn't it 15 years ago when 64k was 
considered more than anyone would need on a micro? Chances are there won't 
be much widespread serious need for anything but small model for a decade 
or two.  It is possible for an OS to not support 32-bit addressing, so an 
application might be stuck with 16-bit addressing.  Also, 32-bit addressing 
makes the code bigger.

Consider 80386 real address mode, or virtual 8086 mode.  In this mode, the
segment register is a number of 16-byte "paragraphs", so that 
physical address = 16 * segment register + offset, rather than a segment
number.  The machine instructions don't provide a carry from the offset
computation into the segment part.

Small model:  pointers are 16 bits, and pointer math works fine. 64k data max.
Large model:  pointers are 32 bits, and pointer math works fine, with no
carries into the segment register.  No object, including arrays, may exceed 64k.
Huge model:  pointers are 32 bits.  Pointer math must propogate carries into
the segment number in a wierd sort of way.  After doing pointer math, it is 
usually necessary to "normalize" the pointer before using it.  Pretending that 
a pointer is a structure, which it's not, normalization can be done by: 
	ptr.seg += ptr.offset >> 4; ptr.offset &= 0xf;  
This is fairly expensive in instructions to compute.  Also, this doesn't 
always work for out-of-range pointers.  

Why normalize?  Consider trying to access a 2-byte quantity at 0x2400:FFFF
( = 0x34FFF).  On a 80386 in real address or virtual 8086 mode, you get a 
General Protection Trap.  On a real 8086, you get one byte from 0x2400:FFFF
and one byte from 0x2400:0000 ( = 0x34FFF and 0x24000), which is wrong.
If you normalize this to 0x33FF:000F, the access works properly.

Now, consider that &foo is at 0x0000:0022.  ( = physical address 0x00022)
&foo[-256] has many representations, the normalized one being 0xFFE2:0002.  
The trouble is, on a 80386 (real address or virtual 8086 mode), adding 256
( * sizeof int) to this (giving 0xFFE2:0202) accesses physical address 
0x100022, which is the wrong memory location.  On a real 8086, this accesses 
physical address 0x00022, which is correct.  (If you don't believe these 
differences, read the 80386's Programmer's Reference Manual, Section 14.7, 
paragraphs 7 and 18.  The 80386 in these modes can access 1 meg + 64k).  This 
part isn't a problem if you don't let the pointer value go outside the array.

The point of this longwinded mess is that in order to handle BOTH > 64k arrays
and arrays with a 0-origin outside array the EVERY access must involve 
pointer arithmetic followed by normalization, and you can't use the
displacement field in instructions, even if it is known that you just
normalized the pointer, and the displacement is small and positive.  Even
if you're trying to access the second half of a 2-byte quantity.  Pointer
normalization is expensive, nearly a dozen instructions.  Just handling
> 64k arrays is bad enough.  Complicating it with out-of-range pointers
makes it much worse.

Microsoft's huge model doesn't handle the full generality required here.
It requires that if you have an array > 128k, that its size be a power of
2.  Guess why these restrictions exist?

I think all of the mentioned characteristics of the 80386 in real-address 
mode or 16-bit protected mode also apply to the 80286.

				Gordon L. Burditt
				...!texbell!sneaky!gordon