Re: HELP ! need to insert value in array !!

Re: HELP ! need to insert value in array !!

[Ralph Silverman]

Lawrence Kirby (fred@genesis.demon.co.uk) wrote:
: In article <5oci49$97g@crl.crl.com> bobfry@crl.crl.com "Robert Fry" writes:

: >Lars <larsiver@post4.tele.dk> writes:
: ...
: >>This works - but is too slow when we are talking about lets say 5000
: >>positions to move...In the "delete" function i use memcopy/memmove and
: >>this appear faster - but offcourse theese functions doesnt work the
: >>other direction...

: memcpy() isn't defined to work at all for overlapping copies, memmove()
: works fine, whether copying backwards or forwards.

: >>Do i have to live with this ? or is there any faster way to push this
: >>array one pos foreward ??

: If you want to stick with arrays you'll have to live with it, insertion
: is simply an inefficient operation on an array. To do better you'll have
: to use a different type of datastructure.

: >Most people I know would use memmove (or memcpy -- I never remember which 
: >one is able to check for conflicts and handle this case). However, I'm 
: >not certain it's portable to all systems.

: Yes, it is.

: >If there's padding between 
: >array elements, you have some potential for problems with memmove.

: An impelemenattion is not permitted to pad between array elements.

: -- 
: -----------------------------------------
: Lawrence Kirby | fred@genesis.demon.co.uk
: Wilts, England | 70734.126@compuserve.com
: -----------------------------------------

	classic theory of sorting
	divide algorithms into two
	related types,
	a)
		primary
		leaf
		internal
	b)	external
		secondary
		etc.

	sorts here discussed are
		primary,  leaf,  internal
	...

	use of
		block move
	instruction(s) in 
		primary sort
	coupled with
	simple ( array )
	data-structure(s)
	is an effective method ...
	and provides very fast
	results ... ( on modern systems )
	...
	( e.g.  pc s manufactured >1989
	  generally incorporate very
	  effective dma ... )

	classic
		computation
	and
		algorithm theory
	generally rest on a
		vonneumann model
	whereby memory transactions
	'shuffle' through cpu ...
	modern methods allow dispacing
	such to 'intelligent' memory
	subsystem ... which acts similarly
	as a peripheral ...
	therefore actual system design
	allows algorithms which might seem
	very inefficient
	( by classic model )
	to be renovated into algorithms
	which are very effective !

--

Ralph Silverman
z007400b@bcfreenet.seflin.lib.fl.us

Re: HELP ! need to insert value in array !!

[Lawrence Kirby]

In article <5p0v7l$9uc@nntp.seflin.org>
           z007400b@bc.seflin.org "Ralph Silverman" writes:

...

>        ( e.g.  pc s manufactured >1989
>          generally incorporate very
>          effective dma ... )

If you are referring to "IBM compatible" PCs the on-board DMA controllers are
*still* dismally slow.

>        classic
>                computation
>        and
>                algorithm theory
>        generally rest on a
>                vonneumann model
>        whereby memory transactions
>        'shuffle' through cpu ...
>        modern methods allow dispacing
>        such to 'intelligent' memory
>        subsystem ... which acts similarly
>        as a peripheral ...
>        therefore actual system design
>        allows algorithms which might seem
>        very inefficient
>        ( by classic model )
>        to be renovated into algorithms
>        which are very effective !

I guess you mean like the sorting networks described in Knuth. What does
this have to do with inserting a value into an array in C?

-- 
-----------------------------------------
Lawrence Kirby | fred@genesis.demon.co.uk
Wilts, England | 70734.126@compuserve.com
-----------------------------------------

Re: HELP ! need to insert value in array !!

[Mike Rubenstein]

dewar@merv.cs.nyu.edu (Robert Dewar) wrote:

> i am not quite sure who said
> 
> <<: An impelemenattion is not permitted to pad between array elements.??
> 
> But it is definitely wrong, of course an implementatoin is permitted
> padding between array elements.
> 

Perhaps it was someone who actually knows C.  Whoever said it was
correct.  Objects may be padded in that there may be bytes that are
not used, but there must be no additional padding between array
elements.  For any type T,

	T a;
	T b[5];

we must have sizeof b == 5 * sizeof a. There can be no unused space
between b[0] and b[1].

Michael M Rubenstein

Re: HELP ! need to insert value in array !!

[Robert Dewar]

Michael says

<<Perhaps it was someone who actually knows C.  Whoever said it was
correct.  Objects may be padded in that there may be bytes that are
not used, but there must be no additional padding between array
elements.  For any type T,

        T a;
        T b[5];

we must have sizeof b == 5 * sizeof a. There can be no unused space
between b[0] and b[1].
>>

Ah, a confusion. I thought the statement was about Ada.

But I am interested in how you could construct a valid ANSI C program
with portable semantics that could detect the difference, and in particular
how exactly the ANSI C standard formally prohibits such "additional padding".
This is the sort of requirement that is very easy to state informally, but
much harder to state formally.

What would one expect on a PDP10 with 5 characters per word and an unused
bit left over, or does the ANSI C standard require 36 bits/character on 
this machine?

<<I don't have the C standard at hand, so i would be interested if someone
could quote chapter and verse on this>>

This sort of statement is the kind of statement that Ada would certainly
like to make in the packed case, but it is hard to make it more than
implementation advice.

I also don't see how your conditoin above can be correct

suppose that type T is a struct with a double field and an int field.
The size of this struct would be 12 bytes, but its alignment requirement
is 8, so it would not be possible to laout the array b without alignment
gaps???

Re: HELP ! need to insert value in array !!

[Mike Rubenstein]

dewar@merv.cs.nyu.edu (Robert Dewar) wrote:

> Michael says
> 
> <<Perhaps it was someone who actually knows C.  Whoever said it was
> correct.  Objects may be padded in that there may be bytes that are
> not used, but there must be no additional padding between array
> elements.  For any type T,
> 
>         T a;
>         T b[5];
> 
> we must have sizeof b == 5 * sizeof a. There can be no unused space
> between b[0] and b[1].
> >>
> 
> Ah, a confusion. I thought the statement was about Ada.
> 
> But I am interested in how you could construct a valid ANSI C program
> with portable semantics that could detect the difference, and in particular
> how exactly the ANSI C standard formally prohibits such "additional padding".
> This is the sort of requirement that is very easy to state informally, but
> much harder to state formally.
> 
> What would one expect on a PDP10 with 5 characters per word and an unused
> bit left over, or does the ANSI C standard require 36 bits/character on 
> this machine?
> 
> <<I don't have the C standard at hand, so i would be interested if someone
> could quote chapter and verse on this>>
> 
> This sort of statement is the kind of statement that Ada would certainly
> like to make in the packed case, but it is hard to make it more than
> implementation advice.
> 
> I also don't see how your conditoin above can be correct
> 
> suppose that type T is a struct with a double field and an int field.
> The size of this struct would be 12 bytes, but its alignment requirement
> is 8, so it would not be possible to laout the array b without alignment
> gaps???
> 

It's quite easy to detect the difference.  For example,

	#include <stdio.h>

	int main(void)
	{
	  int a[2];
	  unsigned long d = (char*) a[1] - (char*) a[0];
	  printf ("%lu %lu\n", d, sizeof(int));
	  return 0;
	}

This must print the same number twice.

Note also that without this rule there would be no guarantee that code
like

	#include <stdlib.h>

	int a[5] = { 1, 2, 3, 4, 5 };;
	int *b = malloc(5 * sizeof *b);
	if (b != NULL)
	  memcpy(b, a, sizeof a);

would work.  It would be extremely difficult for an implementation to
fake this with non-contiguous arrays since the ultimate type of the
allocated memory may not be known at the time the malloc() is done.

From ISO 6.1.2.5:

	An array type describes a contiguously allocated nonempty set 
	of objects ...

This rule is not needed in languages like Ada in which the allocation
can be done by statements or functions that have access to the type
being allocated.  PL/I also does not have this requirement and, in
fact, one does occasionally have arrays with non-contiguous elements.

Michael M Rubenstein

Re: HELP ! need to insert value in array !!

[Robert Dewar]

Michael said

<<It's quite easy to detect the difference.  For example,

        #include <stdio.h>

        int main(void)
        {
          int a[2];
          unsigned long d = (char*) a[1] - (char*) a[0];
          printf ("%lu %lu\n", d, sizeof(int));
          return 0;
        }

This must print the same number twice.
>>


I am unable to prove that the above code has well defined semantics
according to the ANSI standard. The casts of integer pointers into
character pointers seem quite implementation dependent in their
exact meaning to me. In fact it seems quite hard yto implement
this natural semantics on some word oriented machines.

Also, you did not answer my point about alignment. Suppose the array
element type is one whose size is not a multiple of its alignment.
How can gaps be avoided in such a case?

Or are you saying that the ANSI standard requires that the size be a
multiple of the required alignment. If so, please quote chapter and
verse.

It would be useful to know whether you are talking about things that "everyone
knows must be so", or things that are guaranteed to have the semantics you claim
from the standard.

if the latter, relevant references to the standard would be helpful in
following your argument.

Re: HELP ! need to insert value in array !!

[Mike Rubenstein]

dewar@merv.cs.nyu.edu (Robert Dewar) wrote:

> Michael said
> 
> <<It's quite easy to detect the difference.  For example,
> 
>         #include <stdio.h>
> 
>         int main(void)
>         {
>           int a[2];
>           unsigned long d = (char*) a[1] - (char*) a[0];
>           printf ("%lu %lu\n", d, sizeof(int));
>           return 0;
>         }
> 
> This must print the same number twice.
> >>
> 
> 
> I am unable to prove that the above code has well defined semantics
> according to the ANSI standard. The casts of integer pointers into
> character pointers seem quite implementation dependent in their
> exact meaning to me. In fact it seems quite hard yto implement
> this natural semantics on some word oriented machines.
> 
> Also, you did not answer my point about alignment. Suppose the array
> element type is one whose size is not a multiple of its alignment.
> How can gaps be avoided in such a case?
> 
> Or are you saying that the ANSI standard requires that the size be a
> multiple of the required alignment. If so, please quote chapter and
> verse.
> 
> It would be useful to know whether you are talking about things that "everyone
> knows must be so", or things that are guaranteed to have the semantics you claim
> from the standard.
> 
> if the latter, relevant references to the standard would be helpful in
> following your argument.
> 

I am talking about things that are guaranteed in the standard.
Obviously, they are not things that "everyone knows must be so".

I already quoted the relevant passage -- the elements of an array are
contiguous (ISO 6.1.2.5).

If you don't like pointer conversion, consider the program

	int main()
	{
	  int a[10];
	  int b;

	  print("%lu %lu\n", (unsigned long) sizeof a, 
			     10 * (unsigned long) sizeof b);
	  return 0;
	}

No pointer conversion here, but since an array consists of contiguous
elements, this must print the same number twice.  If the elements were
not contiguous, it would print different numbers.

While footnotes are not part of the standard, you might consider
footnote 46 in 6.3.6:

	Another way to approach pointer arithmetic is first to convert

	the pointer(s) to character pointer(s).  In this scheme, the 
	integral expression added to or subtracted from the converted 
	pointer is first multiplied by the size of the object 
	originally pointed to, and the resulting pointer is converted
	back to the original type.  For pointer subtraction, the 
	result of the difference between the character pointers is
	similarly divided by the size of the object originally pointed

	to.

Also consider the example (note, however, that examples are not part
of the standard) in 6.3.4:

	2.  Another use of the sizeof operator is to compute the 
	    number of elements in an array:

`		sizeof array / sizeof array[0]


Michael M Rubenstein

Re: HELP ! need to insert value in array !!

[Ed Hook]

In article <dewar.867608134@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) writes:
|> Michael said
|> 
|> <<It's quite easy to detect the difference.  For example,
|> 
|>         #include <stdio.h>
|> 
|>         int main(void)
|>         {
|>           int a[2];
|>           unsigned long d = (char*) a[1] - (char*) a[0];

   Actually, the line above should probably be:

             unsigned long d = (char *)(a + 1) - (char *)a;

|>           printf ("%lu %lu\n", d, sizeof(int));
|>           return 0;
|>         }
|> 
|> This must print the same number twice.
|> >>
|> 
|> 
|> I am unable to prove that the above code has well defined semantics
|> according to the ANSI standard. The casts of integer pointers into
|> character pointers seem quite implementation dependent in their
|> exact meaning to me. In fact it seems quite hard yto implement
|> this natural semantics on some word oriented machines.
|> 
|> Also, you did not answer my point about alignment. Suppose the array
|> element type is one whose size is not a multiple of its alignment.
|> How can gaps be avoided in such a case?
|>

   The compiler is allowed to insert padding bytes _in_the_element_;
   it's just not permitted to add additional padding _between_ elements.
   That's needed to guarantee (for instance) that an allocation of
   n * sizeof(<type>) bytes can successfully hold an array of n elements
   of type <type>.
 
|> Or are you saying that the ANSI standard requires that the size be a
                                            .allows.
|> multiple of the required alignment. If so, please quote chapter and
|> verse.
|> 

  I don't have a copy of the Standard handy, so I'll let someone else
  provided citations.

|> It would be useful to know whether you are talking about things that "everyone
|> knows must be so", or things that are guaranteed to have the semantics you claim
|> from the standard.
|>

  I'm fairly certain that this (=="no padding between array elements") _is_
  guaranteed by the Standard (but, again, I can't provide the requested
  "chapter and verse").
 
|> if the latter, relevant references to the standard would be helpful in
|> following your argument.
|> 

-- 
 Ed Hook                              |       Copula eam, se non posit
 Computer Sciences Corporation        |         acceptera jocularum.
 NASA Langley Research Center         | Me? Speak for my employer?...<*snort*>
 Internet: hook@cscsun3.larc.nasa.gov |        ... Get a _clue_ !!! ...

Re: HELP ! need to insert value in array !!

[Richard A. O'Keefe]

dewar@merv.cs.nyu.edu (Robert Dewar) writes:

>Also, you did not answer my point about alignment. Suppose the array
>element type is one whose size is not a multiple of its alignment.

There is no such animal in C.  The size of every object *must* be a
multiple of its alignment.

>Or are you saying that the ANSI standard requires that the size be a
>multiple of the required alignment. If so, please quote chapter and
>verse.

My second copy of the C standard seems to have walked off, perhaps to
join its predecessor (wherever _that_ went).  But surely this is one
of the best known aspects of C?  It hasn't changed since Classic C and
is central to the way C pointer arithmetic works.  (Casting (long*) to
(char*) _is_ defined in standard C, by the way.  That's again part of
how pointer arithmetic is defined.)

>It would be useful to know whether you are talking about things that "everyone
>knows must be so", or things that are guaranteed to have the semantics you claim
>from the standard.

I have pruned the list of newsgroups and added comp.std.c, which was
unaccountably missing.


-- 
Four policemen playing jazz on an up escalator in the railway station.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.

Re: HELP ! need to insert value in array !!

[Clive D.W. Feather]

In article <5phtjb$dej$1@goanna.cs.rmit.edu.au>, "Richard A. O'Keefe"
<ok@goanna.cs.rmit.edu.au> writes
>>Also, you did not answer my point about alignment. Suppose the array
>>element type is one whose size is not a multiple of its alignment.
>There is no such animal in C.  The size of every object *must* be a
>multiple of its alignment.

Alignment of a type is *defined* to be the number that addresses of that
object must be a multiple of. Since array elements are exactly sizeof(T)
apart, it is trivial to see that sizeof(T) must be a multiple of the
alignment of T.

WG14 have confirmed that structure/union elements need not have the same
alignment as raw objects of a type, and different structures can put
different alignments on the same type.

>>Or are you saying that the ANSI standard requires that the size be a
>>multiple of the required alignment. If so, please quote chapter and
>>verse.

Definition of alignment is 3.2, IIRC. 3.<small integer> anyway.

That's ISO 3 and current-ANSI 3, not withdrawn-ANSI 3.

-- 
Clive D.W. Feather    | Director of Software Development  | Home email:
Tel: +44 181 371 1138 | Demon Internet Ltd.               | <clive@davros.org>
Fax: +44 181 371 1037 | <clive@demon.net>                 |
Written on my laptop; please observe the Reply-To address |

Re: HELP ! need to insert value in array !!

[Al Bowers]

On Sun, 29 Jun 1997 15:05:28 GMT, miker3@ix.netcom.com (Mike
Rubenstein) wrote:
Referring to C language , I agree with your arguments. However,
the C code you use to reinforce your argument is faulty.

>It's quite easy to detect the difference.  For example,
>
>	#include <stdio.h>
>
>	int main(void)
>	{
>	  int a[2];
>	  unsigned long d = (char*) a[1] - (char*) a[0];
should be:
               unsigned long d = (char *)&a[1] - (char *)&a[0];
or 
               unsigned long d = (char *)(a+1) - (char *)a;
>	  printf ("%lu %lu\n", d, sizeof(int));
               printf("%lu %lu\n",d,(unsigned long)sizeof(int));
>	  return 0;
>	}
>
>This must print the same number twice.
>
>Note also that without this rule there would be no guarantee that code
>like
>
>	#include <stdlib.h>
#include <string.h> /* for memcpy() */
>
>	int a[5] = { 1, 2, 3, 4, 5 };;
                                                  ^^
>	int *b = malloc(5 * sizeof *b);
>	if (b != NULL)
>	  memcpy(b, a, sizeof a);
>
>would work.  It would be extremely difficult for an implementation to
>fake this with non-contiguous arrays since the ultimate type of the
>allocated memory may not be known at the time the malloc() is done.
>
>From ISO 6.1.2.5:
>
>	An array type describes a contiguously allocated nonempty set 
>	of objects ...

Al Bowers                                
Tampa, FL
mailto:abowers@combase.com
http://www.gate.net/~abowers/index.html

Re: HELP ! need to insert value in array !!

[Richard Kenner]

In article <dewar.867589873@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:
>suppose that type T is a struct with a double field and an int field.
>The size of this struct would be 12 bytes, but its alignment requirement
>is 8, so it would not be possible to laout the array b without alignment
>gaps???

No, the size of T would be 16 bytes.  It would be rounded up to a multiple
of its alignment, precisely to avoid problems with an array of them.

Re: HELP ! need to insert value in array !!

[Robert Dewar]

Richard says

<<No, the size of T would be 16 bytes.  It would be rounded up to a multiple
of its alignment, precisely to avoid problems with an array of them.
>>

Richard is talking about the behavior of gcc, which I know well (this
requirement that the size be a multiple of the alignment is an annoying
limitation for Ada, that causes incompatibilities with previous Ada
compilers).

But that's not the question. The question is whether the ANSI C standard
requires this behavor. I must say I have trouble reading the standard,
I don't know it that well, so the fact that I can't prove it is not at
all decisive, but so far no one else has provided the proof either.

Re: HELP ! need to insert value in array !!

[Christian Froeschlin]

Robert Dewar wrote:
> 
> suppose that type T is a struct with a double field and an int 
> field. The size of this struct would be 12 bytes, but its 
> alignment requirement is 8, so it would not be possible to laout 
> the array b without alignment gaps???

Why would the alignment requirement be 8 ? On such a system
an implementation would probably pad the struct (which is allowed),
so sizeof(T) would be 16. 

-- 
   __/  __/   -  Christian Froeschlin
  /    /
 /     _/     * If you eliminate the impossible, whatever remains, *
___/ _/       * however improbable, must be the BUG !              *

Re: HELP ! need to insert value in array !!

[Robert Dewar]

Christian asks

<<Robert Dewar wrote:
>
> suppose that type T is a struct with a double field and an int
> field. The size of this struct would be 12 bytes, but its
> alignment requirement is 8, so it would not be possible to laout
> the array b without alignment gaps???

Why would the alignment requirement be 8 ? On such a system
an implementation would probably pad the struct (which is allowed),
so sizeof(T) would be 16.


Robert replies

The padding has no effect on the alignment requirement, perhaps you
are misunderstanding the term. The alignment of this struct is most
certainly 8, whether or not it is padded.

Re: HELP ! need to insert value in array !!

[Richard A. O'Keefe]

dewar@merv.cs.nyu.edu (Robert Dewar) writes:

>What would one expect on a PDP10 with 5 characters per word and an unused
>bit left over, or does the ANSI C standard require 36 bits/character on 
>this machine?

UCHAR_MAX must be at least 255.  All objects in C must have a size that is
a multiple of the size of a byte, and since we'd expect 36-bit int and
float on a PDP-11, that means the size of a "byte" has to be a factor of
36 that is greater than or equal to 8.  That means the possible sizes for
a char in a PDP-10 implementation of C are
	 9 bits	(4 per word)
	18 bits (2 per word)
	36 bits (1 per word)
I've actually used the Snyder C compiler for the PDP-10, but I can't
remember what it did.  I'm pretty sure it wasn't 9 bits per char.

Note that 5 ASCII characters per word was a software convention; for C
programs to inter-operate with other code, you'd need to convert, but then
for things like opening files you'd need to convert to _six bit_ characters.

>suppose that type T is a struct with a double field and an int field.
>The size of this struct would be 12 bytes, but its alignment requirement
>is 8, so it would not be possible to laout the array b without alignment
>gaps???

The point is that the size of an _isolated_ variable of type T must be
exactly the same as the size of an _array element_ of type T.  Yes, there
would be padding in your type T, but it would be in _all_ variables of
that type, not just ones in an array.  (You could think of every object in
C being an element of a one-element array, and with respect to pointer
arithmetic, that model would not mislead you.)

-- 
Four policemen playing jazz on an up escalator in the railway station.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.

Re: HELP ! need to insert value in array !!

[Robert Dewar]

iRichard O'Keefe said

<<Note that 5 ASCII characters per word was a software convention<<

I think that is wrong, there were hardware instructions on the PDP10 that
used this format, I am pretty sure of this, but it is a while ago ...

Re: HELP ! need to insert value in array !!

[Mike Rubenstein]

dewar@merv.cs.nyu.edu (Robert Dewar) wrote:

> iRichard O'Keefe said
> 
> <<Note that 5 ASCII characters per word was a software convention<<
> 
> I think that is wrong, there were hardware instructions on the PDP10 that
> used this format, I am pretty sure of this, but it is a while ago ...
> 

Not really, at least not in the sense that there were instructions
that handled 7 bit characters specially.  The PDP10 (like its
predecessor the PDP6) had a byte pointer construction that could be
used to access any byte in a word where the byte size was specified as
part of byte pointer.  There was an instruction that would get a byte
and increment the pointer, handling word boundaries properly (a byte
could not be split across words).  Byte pointers and the associated
instructions worked equally well with any byte size up to 36 bits,
though, of course, some word sizes resulted in more wasted bits than
others.

The reason for 7 bit characters was simple -- it was the smallest
standard character size that provied both upper and lower cast.  9 bit
characters would have wasted more memory in text applications of the
time and standard peripherals couldn't handle more than 7 bit ASCII
anyways.  While the maximum memory on early models was 256K 36 bit
words, early machines that large were rather rare on because of the
high cost of memory.

Michael M Rubenstein

Re: HELP ! need to insert value in array !!

[Robert Dewar]

Mike said

<<Not really, at least not in the sense that there were instructions
that handled 7 bit characters specially.  The PDP10 (like its
predecessor the PDP6) had a byte pointer construction that could be
used to access any byte in a word where the byte size was specified as
part of byte pointer.  There was an instruction that would get a byte
and increment the pointer, handling word boundaries properly (a byte
could not be split across words).  Byte pointers and the associated
instructions worked equally well with any byte size up to 36 bits,
though, of course, some word sizes resulted in more wasted bits than
others.
>>

Sure, but why do you think those instructions where there (the ones to
handle odd chunk sizes). The answer is that the motivation was precisely
to allow convenient support of the 7 bit format. The use of these
instructions for any other size was rare. What happened was that there
was a requirement for supporting the 5 char/word format in the hardware,
and the designers generalized it to any byte size (rememebr this was the
hey day of extravagant CISC design).

Given this hardware support though, any compiler not supporting this
format would have been a major menace.

Really the trouble here is the lack of abstraction in the C design when
it comes to arrays. Really there should be a way of saying "allocate
an array of mumbles of length x", but there is no such capability, so
we have to make the assumption that this length can be computed as a
multiple of the element size. 

However, as we see, this assumption has definite shortcomings (e.g.
requiring extra space to be allocated to the use of padded types in
circumstances where this extra space is useless). It sure is interesting
that there definitely seems to be a hole in the standard in that this
requirement is not clearly stated (I would say not stated at all).
This is a gap that should be addressed.

Re: HELP ! need to insert value in array !!

[Larry Kilgallen]

In article <dewar.868107828@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) writes:

> Sure, but why do you think those instructions where there (the ones to
> handle odd chunk sizes). The answer is that the motivation was precisely
> to allow convenient support of the 7 bit format. The use of these
> instructions for any other size was rare. What happened was that there
> was a requirement for supporting the 5 char/word format in the hardware,
> and the designers generalized it to any byte size (rememebr this was the
> hey day of extravagant CISC design).

I would be interested in anything someone have to back up this claim.
I recall viewing 7 bit as just as "odd" as any other size, with 6,
9, 18 and 36 bits as being the most "natural" sizes for the machine.
As I recall all the TOPS-10 (and for that matter, ITS) directory
services were based on SIXBIT.  If the variable byte size capability
was really just an extension from an initial requirement to support
7 bits, I would like to hear the story.

Larry Kilgallen

Re: HELP ! need to insert value in array !!

[Mike Rubenstein]

dewar@merv.cs.nyu.edu (Robert Dewar) wrote:

> Mike said
> 
> <<Not really, at least not in the sense that there were instructions
> that handled 7 bit characters specially.  The PDP10 (like its
> predecessor the PDP6) had a byte pointer construction that could be
> used to access any byte in a word where the byte size was specified as
> part of byte pointer.  There was an instruction that would get a byte
> and increment the pointer, handling word boundaries properly (a byte
> could not be split across words).  Byte pointers and the associated
> instructions worked equally well with any byte size up to 36 bits,
> though, of course, some word sizes resulted in more wasted bits than
> others.
> >>
> 
> Sure, but why do you think those instructions where there (the ones to
> handle odd chunk sizes). The answer is that the motivation was precisely
> to allow convenient support of the 7 bit format. The use of these
> instructions for any other size was rare. What happened was that there
> was a requirement for supporting the 5 char/word format in the hardware,
> and the designers generalized it to any byte size (rememebr this was the
> hey day of extravagant CISC design).

In other words, there were no instructions that specifically supported
7 bit characters, but it was a software convention -- exactly what
Richard and I said.

The byte pointers would have been just as useful had the software used
6 bit characters, which was quite common in those days.  It would also
have been useful for 9 bit characters which were used on Univac and
Honeywell machines.

If the idea had been to use 7 bit characters, why not do it simply by
using a 35 or 42 bit word rather than 36?  Or make the machine byte
addressable with 7 bit bytes?

And, of course, the reason that the byte pointer instructions were
used mostly for 7 bit objects was that the software convention used 7
bit characters.  I doubt if anyone who saw only the instruction set
for the PDP6/10 would immediately recognize that the machine was
designed for 7 bit characters.  In retrospect it seems obvious; after
all, ASCII is a 7 bit code, but in the early 60s when the machine was
designed ASCII was not commonly used as an instruction set on
computers.

On the IBM 709x the most common shifts used were multiples of 6 bits.
Does this mean that shifts were put in to support 6 bit characters?
Of course not -- just the reverse, 6 bit characters made 6 bit shifts
more common.


Michael M Rubenstein

Re: HELP ! need to insert value in array !!

[Mike Rubenstein]

miker3@ix.netcom.com (Mike Rubenstein) wrote:

> And, of course, the reason that the byte pointer instructions were
> used mostly for 7 bit objects was that the software convention used 7
> bit characters.  I doubt if anyone who saw only the instruction set
> for the PDP6/10 would immediately recognize that the machine was
> designed for 7 bit characters.  In retrospect it seems obvious; after
> all, ASCII is a 7 bit code, but in the early 60s when the machine was
> designed ASCII was not commonly used as an instruction set on
> computers.

I meant, of course, that ASCII was not commonly used as a character
set on computers.


Michael M Rubenstein

Re: HELP ! need to insert value in array !!

[Alan Bowler]

In article <dewar.868107828@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:
>Mike said
>
>Sure, but why do you think those instructions where there (the ones to
>handle odd chunk sizes). The answer is that the motivation was precisely
>to allow convenient support of the 7 bit format. The use of these
>instructions for any other size was rare. What happened was that there
>was a requirement for supporting the 5 char/word format in the hardware,
>and the designers generalized it to any byte size (rememebr this was the
>hey day of extravagant CISC design).

Hardly.  The PDP-10 was a very orthogonal design, and compared to
modern systems that call themselves RISC, looks very spartan.  If you
compared it to contemporary systems like the PDP-8 or the CDC-6600
it does look "complex", but it was certainly simpler than the /360.
The PDP-10 had the major RISC attributes many (at least for the time)
identical general registers, fixed length instructions, and no
"indicator register".  (I'm stretching the point on the last a little
it did have overflow and carry bits, but no zero or negative
indicators.)  The 5 byte instructions (load byte, store byte,
load next byte, store next byte and adjust byte pointer were certainly
much simpler than floating square root, floating sine etc that you find
on systems marketed as "RISC" today.

It was the PDP-11 that introduced those complex variable length addressing
modes, and the heyday of CISC only followed that great success.

Re: HELP ! need to insert value in array !!

[Mark H. Wood]

In article <dewar.868049804@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) writes:
> iRichard O'Keefe said
> 
> <<Note that 5 ASCII characters per word was a software convention<<
> 
> I think that is wrong, there were hardware instructions on the PDP10 that
> used this format, I am pretty sure of this, but it is a while ago ...

Nope.  Byte operations on the PDP10 architecture all go through a "byte
pointer" object that can deal with any contiguous collection of 1 to 36 bits
that doesn't cross a 36-bit word boundary.  It's the OS that had a
predisposition for five 7-bit ASCII bytes per word, in string operations. 
Serial I/O hardware had to deal with other realities, but most of it was
slotted into PDP11 frontend processors so it sat behind translation software
anyway.  Interfacing 36-bit hardware with 16-bit hardware made for some
interesting programming (and interesting hardware!), to say the least.
-- 
Mark H. Wood, Lead Systems Programmer    +1 317 274 0749   [@disclaimer@]
MWOOD@INDYVAX.IUPUI.EDU                  Finger for more information.
Thank goodness we've left behind the bad old days, before computers were
transformed from reliable business machines into performance art.

Re: HELP ! need to insert value in array !!

[Robert Dewar]

iMark said

<<

Nope.  Byte operations on the PDP10 architecture all go through a "byte

pointer" object that can deal with any contiguous collection of 1 to 36 bits

that doesn't cross a 36-bit word boundary.  It's the OS that had a

predisposition for five 7-bit ASCII bytes per word, in string operations.

Serial I/O hardware had to deal with other realities, but most of it was

slotted into PDP11 frontend processors so it sat behind translation software

anyway.  Interfacing 36-bit hardware with 16-bit hardware made for some

interesting programming (and interesting hardware!), to say the least.>>

So let's get back to the original thread here, what I said turns
out to be exactly right. The normal format for strings on this machine was 5x7 with one bit lweft over, and there was hardware support for this format. (I
did not say it was the only format supported, just that there was hardware support
for this format and that it was naturally supported in the hardware)

Now back to the original point, given that --- how would you map ANSI C, given
the claims that have been made (actually I can't find real justification
for these claims in the ANSI standeard, and neither can Ritchie)

Re: HELP ! need to insert value in array !!

[Lawrence Kirby]

In article <dewar.868480535@merv> dewar@merv.cs.nyu.edu "Robert Dewar" writes:

>So let's get back to the original thread here, what I said turns
>out to be exactly right. The normal format for strings on this machine was 5x7
> with one bit lweft over, and there was hardware support for this format. (I
>did not say it was the only format supported, just that there was hardware
> support
>for this format and that it was naturally supported in the hardware)
>
>Now back to the original point, given that --- how would you map ANSI C, given
>the claims that have been made (actually I can't find real justification
>for these claims in the ANSI standeard, and neither can Ritchie)

char types in C must be at least 8 bits wide so a 5*7 format fails at that
point. You would probably use a 4*9 format (which is also naturally
supported by the hardware).

-- 
-----------------------------------------
Lawrence Kirby | fred@genesis.demon.co.uk
Wilts, England | 70734.126@compuserve.com
-----------------------------------------

Re: HELP ! need to insert value in array !!

[Shmuel (Seymour J.) Metz]

Robert Dewar wrote:
> 
> iRichard O'Keefe said
> 
> <<Note that 5 ASCII characters per word was a software convention<<
> 
> I think that is wrong, there were hardware instructions on the PDP10 that
> used this format, I am pretty sure of this, but it is a while ago ...

The PDP-6 supported any byte size from 1 to 36, but did not support
bytes that crossed word boundaries. As I recall the instructions were
load byte and deposit byte. The PDP-10 and DEC-System 20 were, of
course, the same architecture and also had those instructions.

-- 

                        Shmuel (Seymour J.) Metz
                        Senior Software SE

The values in from and reply-to are for the benefit of spammers:
reply to domain eds.com, user msustys1.smetz or to domain gsg.eds.com,
user smetz.

Re: HELP ! need to insert value in array !!

[Richard Kenner]

In article <dewar.868049804@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:
>iRichard O'Keefe said
>
><<Note that 5 ASCII characters per word was a software convention<<
>
>I think that is wrong, there were hardware instructions on the PDP10 that
>used this format, I am pretty sure of this, but it is a while ago ...

I'm pretty sure you're wrong.  As far as I recall, tghe byte instructions
on the PDP-10 took a "byte descriptor" that also gave the size of the 
byte.

Re: HELP ! need to insert value in array !!

[Samuel T. Harris]

I believe what is confusing here is that padding
can be inserted for two reasons. One is because of
the natural alignment of the data due to the
particulars of the target machine. The other is due
to some additional particular requirements when making
arrays.

Earlier,

Mike Rubenstein wrote:

> Perhaps it was someone who actually knows C.  Whoever said it was
> correct.  Objects may be padded in that there may be bytes that are
> not used, but there must be no additional padding between array
> elements.  For any type T,
> 
>         T a;
>         T b[5];
> 
> we must have sizeof b == 5 * sizeof a. There can be no unused space
> between b[0] and b[1].
> 
> Michael M Rubenstein

The compiler is allowed to "pad" the elements of the array,
if and only if it "pads" scalar instances of the component
type. Additional padding within the array is not permitted.
This means, in a platform using 32-bit words, a struct taking
11 bits can be placed with 32-bit alignment. This includes
21 bits of "padding". An array of the same struct will
place each 11-bit component in adjacent 32-bit words.
Again, we have 21 bits of "padding" between the "contiguious"
components of the array. This "padding" is natural to the
component since it is natural to the scalar and is not
considered "unused".

Mark sited a standards reference ...

> I am talking about things that are guaranteed in the standard.
> Obviously, they are not things that "everyone knows must be so".
> 
> I already quoted the relevant passage -- the elements of an array are
> contiguous (ISO 6.1.2.5).

his natural "padding" in my example must be 
preserved when creating arrays to satisfy the requirements
and this "padding" does not violate the contiguous nature
of the components in the array.

Robert Dewar also states ...

> i am not quite sure who said
> 
> <<: An impelemenattion is not permitted to pad between array
> elements.??

> But it is definitely wrong, of course an implementatoin is permitted
> padding between array elements.

... in which I believe he is refering to this natural padding.
(Please correct me, Robert, if I've misread you.)
I expect the same default behavior in Ada (except for Booleans).
I want my Ada arrays to lay out similarly to my scalars as
far as alignment is concerned. I don't want my Ada adding
any additional padding.

I use pragma pack when I want Ada to collapse the "natural"
or alignment padding and I expect to pay some performance
penalty when I do so.

-- 
Samuel T. Harris, Senior Engineer
Hughes Training, Inc. - Houston Operations
2224 Bay Area Blvd. Houston, TX 77058-2099
"If you can make it, We can fake it!"