Making Fatal Hidden Assumptions

Motorola 4500- though some bugger will probably write one just to prove me wrong.

Paul Burke

Reply to
Paul Burke
Loading thread data ...

Wrong. There is one. It's *very* small, but it's still required to be there.

I'll have to call that one. I challenge you to name at least one platform where the library requirements for freestanding implementations make it noticeably harder to implement C.

--
Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.
Reply to
Hans-Bernhard Broeker

Just because the library is *available* to the compiler, does not mean that it has to be included on the target. So the library can be as huge as you like, and not increase the size of the runtime. Of course you do then need to be aware of the consequences of, e.g., an inadvertant printf!

--

John Devereux
Reply to
John Devereux

To be fair, though, I suspect that bit reversed addressing is a bit over-rated, within the DSP community. If I were designing a new DSP processor, I'd be very tempted to leave it out, unless the instruction space, die space and cycle-time impact it introduced were completely negligible. In many ordinary processors you can perform a bit-reverse re-ordering in about 10% of the cost of performing the FFT itself with ordinary instructions (see below), recursive counting code, or a lookup table (for smallish FFT sizes, probably less for larger). FFTW manages to hold many performance benchmark crowns while producing in-order results on conventional processors. Besides which, not all FFT algorithms produce results in bit-reverse order anyway.

As an example of the sort of algorithmic weirdness that is sometimes put into hardware, for which there isn't a good, let alone convenient way to express in C, it's pretty good.

For the non-DSP-inclined, here's a simple expression of a bit-reverse increment operation, in C:

unsigned int bitrev_inc(unsigned int i, unsigned int N) { return (N & i) ? bitrev_inc(i ^ N, N >> 1) : i ^ N; }

That one needs to be called with N = bins/2 where bins is the size of the FFT, a power of 2. It's not especially efficient, but it is at least a single pure function, and GCC does a good job on the tail recursion. An iteration over an array could use i = bitrev_inc(i, bins/2) as an index increment operation. It could be coded iteratively as a loop around while(N & i), but that seems to be even more of a stretch for a compiler to recognize as simply the invocation of an addressing mode.

Cheers,

--
Andrew
Reply to
Andrew Reilly

In article "Ed Prochak" writes: ... > I would agree that if an assembler must be a one-to-one mapping from > source line to opcode, then C doesn't fit. I just don't agree with that > definition of assembler.

On the other hand for every machine instruction there should be an construct in the assembler to get that instruction. With that in mind C doesn't fit either.

--
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/
Reply to
Dik T. Winter

...

...

By the same logic, ptr to just past the end of an array (which, of course, does not point to an object), _can_ compare equal to null ptr? ;-)

- Of course not, semantics for "==" guarantee that both ptrs must be null (among others) to compare equal.

AFAIK the one-past-the-end ptrs were introduced to enable certain idioms, and as such are not a necessity in the language: while (*dest++ = *src++) ; /* strcpy-like */ IMHO the language could also use the concept of one-before-the-start pointers for similar purposes, but it doesn't for practical (and good) reasons. Here's what C99 Rationale says (6.5.6):

: In the case of p-1, on the other hand, an entire object would have : to be allocated prior to the array of objects that p traverses, : so decrement loops that run off the bottom of an array can fail. : This restriction allows segmented architectures, for instance, to : place objects at the start of a range of addressable memory.

--
Stan Tobias
mailx `echo siXtY@FamOuS.BedBuG.pAlS.INVALID | sed s/[[:upper:]]//g`
Reply to
S.Tobias

I don't fully understand what you are saying here. Please elaborate. At first I thought maybe you meant that you can find no documented case of an implementation that has an 8 bit int, then I thought, well MAYBE, he means that it aint 'C' if it has an 8 bit int........

Jim

Reply to
James Beck

Over the years, there have been notable cases of "hidden" machine instructions -- undocumented instructions, quite possibly with no assembler construct (at least not in any publically available assembler.)

--
Programming is what happens while you're busy making other plans.
Reply to
Walter Roberson

C is an assembler because

-- It doesn't impose strict data type checking, especially between integers and pointers. (While there has been some discussion about cases where conversions back and forth between them can fail, for most machines it works. Good thing too or some OS's would be written in some other language.)

-- datatype sizes are dependent on the underlying hardware. While a lot of modern hardware has formed around the common 8bit char, and multiples of 16 for int types (and recent C standards have started to impose these standards), C still supports machines that used 9bit char and 18bit and 36bit integers. This was the most frustrating thing for me when I first learned C. It forces precisely some of the hidden assumptions of this topic.

-- C allows for easy "compilation" in that you could do it in one pass of the source code (well two counting the preprocessor run). The original C compiler was written in C so that bootstrapping onto a new machine required only a simple easily written initial compiler to compile the real compiler.

-- original versions of the C compiler did not have passes like data-flow optimizers. So optimization was left to the programmer. Hence things like x++ and register storage became part of the language. Perhaps they are not needed now, but dropping these features from the language will nearly make it a differrent language. I do not know of any other HLL that has register, but about every assembler allows access to the registers under programmer control.

So IMHO, C is a nice generic assembler. It fits nicely in the narrow world between hardware and applications. The fact that it is a decent application development language is a bonus. I like C, I use it often. Just realize it is a HLL with an assembler side too.

Ed

Reply to
Ed Prochak

I'll have to call that one. Which part of the standard C library is required?

Sorry you lost me. Until we clear up exactly what this library is I can hardly answer this question.

Ian

Reply to
Ian Bell

I agree 100%. if you do not link to any of the library then none of it will be in the implementation. So as I said if you don't want it you don't have to use it.

Ian

Reply to
Ian Bell

My copy of "C: The Complete Reference" has this to say : "The proposed ANSI standard has defined both the content and the form of the standard library. However, certain parts of that library may not be found in your implementation for various reasons." So, hmmmmmmm, it has to be there and yet it doesn't have to be complete? Kinda' ambiguous, isn't that what the standard was suppose to stop? I know my "good" cross compilers implement the entire stdlib, even if the function is just a stub that returns a NULL or some other failure value if the feature is not supported.

Jim

Reply to
James Beck

"Ed Prochak" writes: [...]

Incorrect. Attempting to assign an integer value to a pointer object, or vice versa, is a constraint violation, requiring a diagnostic. Integer and pointers can be converted back and forth only using a cast (an explicit conversion operator). The result of such a conversion is implementation-defined.

Even if this were correct, it certainly wouldn't make C an assembler.

I don't know what "recent C standards" you're referring to. C requires CHAR_BIT to be at least 8; it can be larger. short and int must be at least 16 bits, and long must be at least 32 bits. A conforming implementation, even with the most current standard, could have 9-bit char, 18-bit short, 36-bit int, and 72-bit long.

But this is a common feature of many high-level languages. Ada, for example has an implementation-defined set of integer types, similar to what C provides; I've never heard anyone claim that Ada is an assembler.

You're talking about an implementation, not the language.

Again, you're talking about an implementation, not the language.

C doesn't allow access to specific registers (at least not portably).

Here's what the C standard says about the "register" specifier:

A declaration of an identifier for an object with storage-class specifier register suggests that access to the object be as fast as possible. The extent to which such suggestions are effective is implementation-defined.

And there are a few restrictions; for example, you can't take the address of a register-qualified object.

You've given a few examples that purport to demonstrate that C is an assembler.

Try giving a definition of the word "assembler". If the definition applies to C (the language, not any particular implementation), I'd say it's likely to be a poor definition, but I'm willing to be surprised.

--
Keith Thompson (The_Other_Keith) kst-u@mib.org  
San Diego Supercomputer Center               
 Click to see the full signature
Reply to
Keith Thompson

"A conforming freestanding implementation shall accept any strictly conforming program that does not use complex types and in which the use of the features specified in the library clause (clause 7) is confined to the contents of the standard headers , , , , , , and ."

--
John W. Temples, III
Reply to
John Temples

On many processors, particularly the 8 and 16-bit micros, but also some

32-bit RISCs, there is a necessary library that contains functions for the arithmetic operators that don't necessarily translate into discrete instructions. Division operations are probably a good example. Long integer arithmetic might require (or just use) subroutines. Some systems use subroutines to save and restore callee-saved registers, when code size is more important than speed. Floating point is frequently done with subroutine libraries (or OS traps, on bigger integer-only systems).

It's still true that you can often arrange to code so that none of these get invoked, and therefore dragged into the executable, but there's a spectrum, and on some processors it's pretty nigh impossible to avoid.

Cheers,

--
Andrew
Reply to
Andrew Reilly

Well, since we're talking about a "universal assembler" (a reasonably commonly used term), that's obviously something different from the usual machine-specific assembler, which does indeed usually have that property. (Although I've met assemblers where the only way to get certain instructions was to insert the data for the op-code in-line. Instruction coverage sometimes lags behind features added to actual implementations.)

--
Andrew
Reply to
Andrew Reilly

Those headers essentially only define typedefs and constants. That's not much of a library requirement, in the "link-to" and "consume program memory" sense, is it?

--
Andrew
Reply to
Andrew Reilly

In article snipped-for-privacy@ibd.nrc-cnrc.gc.ca (Walter Roberson) writes: > In article , Dik T. Winter wrote: > >In article "Ed Prochak" writes: > > > > I would agree that if an assembler must be a one-to-one mapping from > > > source line to opcode, then C doesn't fit. I just don't agree with that > > > definition of assembler. > > >On the other hand for every machine instruction there should be an > >construct in the assembler to get that instruction. With that in > >mind C doesn't fit either. > > Over the years, there have been notable cases of "hidden" machine > instructions -- undocumented instructions, quite possibly with no > assembler construct (at least not in any publically available > assembler.)

Indeed. But even when we look at the published instructions C falls short of providing a construct for every one. Where is the C construct to do a multply step available in quite a few early RISC machines? Note also that in assembler you can access the special bits indicating overflow and whatever (if they are available on the machine). How to do that in C?

--
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/
Reply to
Dik T. Winter

In article "Ed Prochak" writes: ... > C is an assembler because > > -- It doesn't impose strict data type checking, especially between > integers and pointers. > (While there has been some discussion about cases where conversions > back and forth between them can fail, for most machines it works. Good > thing too or some OS's would be written in some other language.)

It does impose restrictions. You have to put in a cast.

The same is true for Pascal.

What is valid for C is also valid for Pascal. But not all is valid. Code generation, for instance, is *not* part of the compiler. Without a back-end that translates the code generated by the compiler to actual machine instructions, you are still nowhere. So your simple easily written initial compiler was not an easily written initial compiler. You have to consider what you use as assembler as backend. In contrast the very first Pascal compiler was really single-pass and generated machine code on-the-fly, without backend. Everything ready to run. (BTW, on that machine the linking stage was almost never pre-performed, it took only a few milli-seconds.)

In C "register" is only a suggestion, it is not necessary to follow it. On the other hand, the very first Pascal compiler already did optimisation, but not as a separte pass, but as part of the single pass it had. You could tweek quite a bit with it when you had access to the source of the compiler.

--
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/
Reply to
Dik T. Winter

In article Andrew Reilly writes: > On Mon, 13 Mar 2006 15:31:35 +0000, Dik T. Winter wrote: ... > > On the other hand for every machine instruction there should be an > > construct in the assembler to get that instruction. With that in > > mind C doesn't fit either. > > Well, since we're talking about a "universal assembler" (a reasonably > commonly used term), that's obviously something different from the usual > machine-specific assembler, which does indeed usually have that property. > (Although I've met assemblers where the only way to get certain > instructions was to insert the data for the op-code in-line. Instruction > coverage sometimes lags behind features added to actual implementations.)

I have met one such, but not for the reason you think. In this case the assembler knew the instruction, and translated it, but completely wrong. Apparently an instruction never used, but nevertheless published. And I needed it.

But what is (in your opinion) a universal assembler? What properties should it have to contrast it with a HLL?

--
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/
Reply to
Dik T. Winter

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.