The C LanguageCOMS W4995-02Prof. Stephen A. EdwardsFall 2002Columbia UniversityDepartment of Computer ScienceThe C LanguageCurrently, the mostcommonly-used language forembedded systems”High-level assembly”Very portable: compilersexist for virtually everyprocessorEasy-to-understandcompilationProduces efficient codeFairly conciseC HistoryDeveloped between 1969 and 1973 alongwith UnixDue mostly to Dennis RitchieDesigned for systems programming•Operating systems•Utility programs•Compilers•FiltersEvolved from B, which evolved from BCPLBCPLMartin Richards, Cambridge, 1967Typeless•Everything a machine word (n-bit integer)•Pointers (addresses) and integers identicalMemory: undifferentiated array of wordsNatural model for word-addressed machinesLocal variables depend on frame-pointer-relativeaddressing: no dynamically-sized automatic objectsStrings awkward: Routines expand and pack bytes to/fromword arraysC HistoryOriginal machine (DECPDP-11) was very small:24K bytes of memory, 12Kused for operating systemWritten when computerswere big, capital equipmentGroup would get one,develop new language, OSC HistoryMany language features designed to reduce memory•Forward declarations required for everything•Designed to work in one pass: must know everything•No function nestingPDP-11 was byte-addressed•Now standard•Meant BCPL’s word-based model was insufficientEuclid’s Algorithm in Cint gcd(int m, int n ){int r;while ((r = m % n) != 0) {m = n;n = r;}return n;}“New syle” functiondeclaration listsnumber and type ofarguments.Originally onlylisted return type.Generated code didnot care how manyarguments wereactually passed,and everything wasa word.Arguments arecall-by-valueEuclid’s Algorithm in Cint gcd(int m, int n ){int r;while ((r = m % n) != 0) {m = n;n = r;}return n;}Automatic variableAllocated on stackwhen functionentered, releasedon returnParameters &automatic variablesaccessed via framepointerOther temporariesalso stacked← IgnorednmFP → PCr → SPEuclid on the PDP-11.globl gcd GPRs: r0–r7.text r7=PC, r6=SP, r5=FPgcd:jsr r5, rsave Save SP in FPL2: mov 4(r5), r1 r1 = nsxt r0 sign extenddiv 6(r5), r0 r0, r1 = m ÷ nmov r1, -10(r5) r = r1 (m % n)jeq L3 if r == 0 goto L3mov 6(r5), 4(r5) m = nmov -10(r5), 6(r5) n = rjbr L2L3: mov 6(r5), r0 r0 = njbr L1 non-optimizing compilerL1: jmp rretrn return r0 (n)Euclid on the PDP-11.globl gcd.textgcd:jsr r5, rsaveL2: mov 4(r5), r1sxt r0div 6(r5), r0mov r1, -10(r5)jeq L3mov 6(r5), 4(r5)mov -10(r5), 6(r5)jbr L2L3: mov 6(r5), r0jbr L1L1: jmp rretrnVery naturalmapping fromC into PDP-11instructions.Complex addressing modesmake frame-pointer-relativeaccesses easy.Another idiosyncrasy:registers werememory-mapped, so takingaddress of a variable in aregister is straightforward.Pieces of CTypes and Variables•Definitions of data in memoryExpressions•Arithmetic, logical, and assignment operators in aninfix notationStatements•Sequences of conditional, iteration, and branchinginstructionsFunctions•Groups of statements invoked recursivelyC TypesBasic types: char, int, float, and doubleMeant to match the processor’s native types•Natural translation into assembly•Fundamentally nonportable: a function of processorarchitectureDeclaratorsDeclaration: string of specifiers followed by a declaratorstatic unsignedbasic typez}|{int| {z }specifiers(*f[10])(int, char*)[10];| {z }declaratorDeclarator’s notation matches that of an expression: use itto return the basic type.Largely regarded as the worst syntactic aspect of C: bothpre- (pointers) and postfix operators (arrays, functions).Struct bit-fieldsAggressively packs data into memorystruct {unsigned int baud : 5;unsigned int div2 : 1;unsigned int use_external_clock : 1;} flags;Compiler will pack these fields into words.Implementation-dependent packing, ordering, etc.Usually not very efficient: requires masking, shifting, andread-modify-write operations.Code generated by bit fieldsstruct {unsigned int a : 5;unsigned int b : 2;unsigned int c : 3;} flags;void foo(int c) {unsigned int b1 =flags.b;flags.c = c;}# unsigned int b1 = flags.bmovb flags, %alshrb 5, %almovzbl %al, %eaxandl 3, %eaxmovl %eax, -4(%ebp)# flags.c = c;movl flags, %eaxmovl 8(%ebp), %edxandl 7, %edxsall 7, %edxandl -897, %eaxorl %edx, %eaxmovl %eax, flagsC UnionsLike structs, but only stores the most-recently-writtenfield.union {int ival;float fval;char *sval;} u;Useful for arrays of dissimilar objectsPotentially very dangerous: not type-safeGood example of C’s philosophy: Provide powerfulmechanisms that can be abusedLayout of Records and UnionsModern processors have byte-addressable memory.01234Many data types (integers, addresses, floating-pointnumbers) are wider than a byte.16-bit integer: 1 032-bit integer: 3 2 1 0Layout of Records and UnionsModern memory systems read data in 32-, 64-, or 128-bitchunks:3 2 1 07 6 5 411 10 9 8Reading an aligned 32-bit value is fast: a single operation.3 2 1 07 6 5 411 10 9 8Layout of Records and UnionsSlower to read an unaligned value: two reads plus shift.3 2 1 07 6 5 411 10 9 86 5 4 3SPARC prohibits unaligned accesses.MIPS has special unaligned load/store instructions.x86, 68k run more slowly with unaligned accesses.Layout of Records and UnionsMost languages “pad” the layout of records to ensurealignment restrictions.struct padded {int x; /* 4 bytes */char z; /* 1 byte */short y; /* 2 bytes */char w; /* 1 byte */};x x x xy y zw= Added paddingC Storage Classes/* fixed address: visible to other files */int global static;/* fixed address: only visible within file */static int file static;/* parameters always stacked */int foo(int auto param){/* fixed address: only visible to function */static int func static;/* stacked: only visible to function */int auto i, auto a[10];/* array explicitly allocated on heap (pointer stacked) */double *auto d =malloc(sizeof(double)*5);/* return value passed in register or stack */return auto i;}malloc() and free()Library routines for managing the heapint *a;a = (int *) malloc(sizeof(int) * k);a[5] = 3;free(a);Allocate and free arbitrary-sized chunks of memory in anyordermalloc() and free()More flexible than (stacked) automatic variablesMore costly in time and spacemalloc() and free() use non-constant-time algorithmsTwo-word overhead for each allocated block:•Pointer to next empty block•Size of this blockCommon source of errors:Using uninitialized memory Using freed memoryNot allocating enough Indexing past blockNeglecting to free