Decrement a given pointer.

[Ken Brody]

Not in the context of the OP, the address p-1 was never dereferenced.

It doesn't matter. Simply loading an invalid address (which is likely to
happen when it calculates the value of "p-1") into the register can cause a
fault.

 

[glen herrmannsfeldt]

On 7/8/2013 9:14 PM, Ian Collins wrote:
(snip)

It doesn't matter. Simply loading an invalid address
(which is likely to happen when it calculates the value of "p-1")
into the register can cause a fault.

Well it can, but for systems where that is true, and where the
computation can (or must) be done in other registers, it is usual
to do it such that it won't cause a fault.

Some time ago I was considering the problem of a C compiler
generating JVM code. The JVM 'reference' is opaque. There is no
operation that will increment or decrement such an object.
The offset is supplied at dereference time.

JVM code to represent a C pointer would have an origin
(reference object) and offset.

Note also the C restriction on comparing pointers to different
objects. In large model x86, the compiler only compares the offset.
If you use a relational operator on different object, the result
may be surprising.

Even if the implementation does fault on generating an invalid
address, all the C compiler has to do is be sure not to generate
such an address until it is actually time to dereference it.
That is, keep the origin and offset separate. There is a good
chance that the system will require that, anyway.

-- glen

 

[Joe Pfeiffer]

(snip)

Indexing into a heap. The top of the heap is heap[1].
The two subsidiary nodes to heap[k] are
heap[2 * k] and heap[2 * k + 1]. [...]

To be clear, the word "heap" is used for two unrelated things, the data
structure Michael is talking about, and the region of memory from which
malloc() allocates.

It took me a few seconds to notice that on the first post mentioning it.
It has been many years since I wrote a heapsort for an undergrad
programming assignment. Haven't done any heaps since.

Also, note that the former is often stored in the latter.
There should be a name for that.

Beyond "source of much student confusion"?

 

[glen herrmannsfeldt]

(snip, someone wrote)
(then I wrote)

I don't think it did. MSC 6.0 or thereabouts was the last one that
did, IIRC.

I think about then I started using the Watcom compilers.
(Both 16 bit and 32 bit compilers.)

Certainly not an uncommon technique. Actual huge pointers were
sloooow.

Well, yes, but even so every segment selector load requires
the processor to load the 8 byte segment descriptor.
(As far as I know, none of the processors would notice that the
selector was the same and not reload. Even more, they could have
put in a cache of recent segment selectors to avoid the cost
of reloading them.)

Mainly ones having to do with keeping pointers in registers between
uses and modifications - in VC1.5 huge pointers seem to flush to
memory at pretty much any point where the might be modified. That
certainly keeps the invalid values out of the segment registers until
you actually use them for addressing.

Well, for one on the 286 and 386 there was only ES to use.
(At least it was usual to keep DS mostly constant throughout
a function.) Later FS and GS were added, but late enough that
they didn't get used much.

Besides that, there weren't many registers. You might keep
something in DX for a little while, but not for long.

-- glen

 

[Nobody]

Indexing into a heap. The top of the heap is heap[1].
The two subsidiary nodes to heap[k] are
heap[2 * k] and heap[2 * k + 1].

If you subtract one from all indices, you get:

The top of the heap is heap[1-1] == heap[0]
The two subsidiary nodes to heap[k-1] are
heap[2*k-1] == heap[2*(k-1)+1] and
heap[2*k+1-1] == heap[2*k] == heap[2*(k-1)+2]

Substituting k-1 == u gives:

The top of the heap is heap[0]
The two subsidiary nodes to heap are
heap[2 * u + 1] and heap[2 * u + 2]

 

[James Kuyper]

On Wed, 10 Jul 2013 06:41:08 -0400, James Kuyper



C for Clearpath IX (the old Univac 1100/2200 ISA) does 9 bit chars.
It's also one's complement, and has 18/36/72 bit
shorts/ints+longs/longlongs. Float and double are 36 and 72 bits as
well. It's an actual real and current implementation, although rather
out of the mainstream.

In many previous discussions of C implementations with CHAR_BIT==9, I
and others have asked for examples of such implementations, and all we
got was silence. However, as soon as I say there are none, several
examples are given. That says something a bit annoying about human
psychology.

 

[Les Cargill]

In many previous discussions of C implementations with CHAR_BIT==9, I
and others have asked for examples of such implementations, and all we
got was silence. However, as soon as I say there are none, several
examples are given. That says something a bit annoying about human
psychology.

Memory seems to work like peripheral vision - trying to remember
in a focused fashion seems less effective than thinking
about something else. It's as if your brain dispatches an
archivist to go find it, and that takes a little
while.

 

[Stephen Sprunk]

Not correct on this last point; you could put any random garbage into
a 68000 address register, and it wouldn't fault (at least, unless you
actually tried to reference it; what it would then do would depend on
whatever MMU or memory bus you have hooked up)

I meant that having dedicated address registers meant it could have done
so, not that any given implementation actually did so.

S

 

[Eric Sosman]

Consider an optimizing compiler:

int array [10];
for (int* p = &array [9]; p >= &array [0]; --p) ....

After reaching &array [0], decrementing p is undefined behaviour. p >= &array [0] is always true unless there is undefined behaviour. So the compiler can assume it is always true, and the loop never ends. Until the application crashes.

int array [10];
int* p = &array [0] - 1;

Subtracting 1 from &array [0] is undefined behaviour. The compiler can assume there is no undefined behaviour, so it's absolutely fine for the compiler to set p to &array [0].

static int array [10];
int f (int* p) { int* q = p - 1; return (p == &array [0]); }

Subtracting 1 from a pointer to the first element of an array is undefined behaviour. The compiler can assume there is no undefined behaviour, so p == &array [0] must be false.

In the example, the undefined behaviour is clearly visible to the compiler, so expect the worst.

If this degree of optimizer "reasoning" seems far-fetched,
it's not. See

<http://www.theregister.co.uk/2009/07/17/linux_kernel_exploit/>

.... for an example that matches none of Christian's, but is quite
similar in spirit:

- A pointer was dereferenced, and later checked for NULLness.

- If the pointer were NULL, the dereference would invoke
undefined behavior.

- If the behavior was undefined, then it didn't matter how
the subsequent NULLness test came out: Any result (even *no*
result) would be permitted.

- The NULLness test was therefore superfluous.

- ... so the optimizer removed it.

And, of course:

- Linux developers blamed gcc for their own misteak.

 

[Michael Press]

[heap as a motivating example for using 1 offset arrays]

The only neat way to run a heap is with a 1 offset array.

It is a neat way, but not the only neat way. Using a 0 offset
array with the property that a >= a[2*i] and a >= a[2*i+1]
has the nice consequence that a[0] is the largest element and
a[1] is the second largest element. This relationship can be
used to implement, eg, a slightly more efficient heapsort.

Thanks. I will look into it.