These are random notes in reviewing C/C++.

The C Language

C language history and purpose

• Before UNIX, most OS were written in assembly language, tying them to specific instruction set architecture (ISA)
• An assembly language program is a sequence of ISA instructions
• C was created by Dennis Ritchie at Bell Labs in 1972 to have characteristics of a “High-level” assembly language
• C was intended to make Unix easier to port to different ISAs
  • Only about 5% of Unix is written in assembly language
  • 95% of Unix is written in C (Requiring a C compiler for the ISA)
• Just the assembly language 5% must be rewritten and a C compiler written to migrate Unix to another machine ISA

Some uses of C

• Linux is written in C
• Low-level libraries that need speed are typically written in C. string handling, math routines, windowing, graphics, MP3 decoders
• Games often written in C
• Java runs on JVM Java Virtual Machine which is written in C
• C is used for performance-critical
  • Java native libraries in C include user interface, database access, animation, math, etc

The C design principle

• C does not get in the way of a program running fast
• For example, consider the array access a[i] = value;
• Java bytecode executed is equivalent to checking array boundaries before assignment; therefore can throw out of bound exceptions
• C code compiles to machine code equivalent to a[i]=value; there are no array bound checks
• With C, no run time is used to prevent writing to an out of bounds memory location

Vulnerabilities arising in C

• An array access out of bounds error is very difficult to debug
  • The assignment may happen in a different variable located in memory just after the array (see example slide)
• That which makes C programs fast can also make them vulnerable to safety problems

The C design principle revisited

• C does not get in the way of program running fast, however C will not protect you if you make a mistake
• Programming and debugging in C is more difficult, time consuming than Java
• Java is used for applications requiring less processor work and perhaps more input/output
  • Webapps
• C is used for processor-intensive applications

Java garbage collection and C memory management

• JVM garbage collection removes data objects from memory
• C programs use explicit memory management
  • The call p=malloc(size) allocates space in memory for p
• malloc(p) must be paried with a call to free(p) when object p is no longer in use
  • Forgetting to call free(p) causes memory leak
  • Ongoing memory leaks slow execution and may cause crash
• Calling free(p) before the final use of is a premature free
  • Writing to p after premature free can corrupt memory allocation data structures and cause crash
• Memory allocation errors make programming in C more difficult

Memory use in Java and C

• C programs typically use less than half as much space in memory than Java
• C program can be fast and small, but must be written with care
• In general, try to write in Java, C#, Python
• Only if speed is essential use C or C++

Compiling C Program

• Compile with this command

gcc -o hello hello.c
-o = make hello the executable file

• Also may compile using commands options

gcc -g -o hello hello.c
-g = compile to permit use of the gbd debugging tool
gcc -std=gnu99 -o hello hello.c
-std=gnu99 = use GNU C99 C language definition

• Run program hello 

./hello

Some C commands

• <stdio.h> = to do i/o
• printf() = stdout
• scanf() = stdin
• putchar(c) = sends character to stdout
• getchar(c) = read char from stdin; to exit must pass <ctrl-D> which indicates EOF
• for(f=0;f<=300;f+=0) {}
• Can use getchar(c) to 
  • Count characters
  • Count newlines

if (c==’\n’) nlines++;

• • Count words

if (c==’\n’ || c==’ ‘ || c==’\t’)

• • Count digits

if (c >= ‘0’ && c <=’9’)

• • With getchar() we can create our own grep

#include <stdlib.h>
FILE * fd = fopen(fileName,”r”);  // open file
if (fd == NULL) { //error
while(fgets(line, MAXLINE, fd) != NULL) { // get file line
if (strstr(line,pattern) != NULL) { // string in string

C Function Declarations

A function declaration tells the compiler about a function name and how to call the function. The actual body of the function can be defined separately. A function declaration has the following parts −

return_type function_name( parameter list );

 

Example:

int max(int num1, int num2);

Parameter names are not important in function declaration only their type is required, so the following is also a valid declaration −

int max(int, int);

Function declaration is required when you define a function in one source file and you call that function in another file. In such case, you should declare the function at the top of the file calling the function.

 

Examples of C operators, statements, commands, logic …

Conditions

#!/bin/bash
directory="./Scripting"
# if statement to check if directory exists
if [ -d $directory ]; then
    echo "Directory exists"
elif [ -a $directory ]; then
    Echo “File exists, but is not a directory”
else
    echo "Directory does not exist"
fi

Brackets do not touch variables. 

 

Pipes

#!/bin/bash
echo "Retrieving data about" $USER
who | grep $USER

To get list of all environment variables use command printenv

#!/bin/bash
echo $HOME
echo $PATH
echo $USER

 

Arguments

#!/bin/bash
echo $1 $2 $3

The above is using positional parameters. 

Parameter(s)	Description
$0	the first positional parameter, equivalent to argv[0] in C, see the first argument
$FUNCNAME	the function name (attention: inside a function, $0 is still the $0 of the shell, not the function name)
$1 … $9	the argument list elements from 1 to 9
${10} … ${N}	the argument list elements beyond 9 (note the parameter expansion syntax!)
$*	all positional parameters except $0, see mass usage
$@	all positional parameters except $0, see mass usage
$#	the number of arguments, not counting $0

 

File/Directory Checks

if [[ -d $PASSED ]]; then 
  echo "$PASSED is a directory" 
elif [[ -f $PASSED ]]; then 
  echo "$PASSED is a file" 
else 
  echo "$PASSED is not valid" 
  exit 1 
fi

Double square brackets is a bash extension to [ ]. It doesn’t require variables to be quoted, not even if they contain spaces.

#!/bin/bash
echo Hello there people! > outfile.txt
cat < outfile.txt

File appending

#!/bin/bash
echo "Hello $USER!!" > tmp-message
echo >> tmp-message
echo "Today is" `date` >> tmp-message
echo >> tmp-message
echo "Sincerely," >> tmp-message
echo " Myself" >> tmp-message
/usr/bin/mailx -s "mail-hello" $USER < tmp-message
echo "Message sent."

 

Loops

#!/bin/bash
# for loop
for f in $( ls /var/ ); do
    echo $f
done
COUNT=6
# while loop
while [ $COUNT -gt 0 ]; do
   echo Count: $COUNT
   let COUNT=COUNT-1
done

 

Escape Sequences

Escape sequence Action

\n prints a new line
\b backs up one character
\t moves the output position to the next tab stop
\\ prints a backslash
\" prints a double quote
\' prints a single quote

printf() Parameters

%d Print an integer number printed in decimal (preceded by a minus sign if the number is negative).
%f Print a floating point number ( in the form dddd.dddddd).
%E Print a floating point number ( in scientific notation: d.dddEddd).
%g Print a floating point number (either as f or E, depending on value and precision).
%x Print an integer number in hexadecimal with lower case letters.
%X Print an integer number printed in hexadecimal with upper case letters.
%c Print a character.
%s Print a string.

C struct

In C programming, a struct (or structure) is a collection of variables (can be of different types) under a single name.

struct structureName {
  dataType member1;
  dataType member2;
  ...
};

struct Person {
  char name[50];
  int citNo;
  float salary;
};

We use the typedef keyword to create an alias name for data types. It is commonly used with structures to simplify the syntax of declaring variables.

struct Distance{
  int feet;
  float inch;
};

int main() {
 struct Distance d1, d2;
}
// Using typedef

typedef struct Distance {
  int feet;
  float inch;
} distances;

int main() {
  distances d1, d2;
}

There are two types of operators used for accessing members of a structure.

• “.” Member operator

person2.salary

• “->” To access members of a structure using pointers

 

Example of Struct with Pointers

#include <stdio.h>
struct person
{
   int age;
   float weight;
};

int main()
{
    struct person *personPtr, person1;
    personPtr = &person1;   
    printf("Enter age: ");
    scanf("%d", &personPtr->age);
    printf("Enter weight: ");
    scanf("%f", &personPtr->weight);
    printf("Displaying:\n");
    printf("Age: %d\n", personPtr->age);
    printf("weight: %f", personPtr->weight);
    return 0;
}

size_t

size_t is an unsigned integral data type which is defined in various header files such as: 

It’s a type which is used to represent the size of objects in bytes and is therefore used as the return type by the sizeof operator. It is guaranteed to be big enough to contain the size of the biggest object the host system can handle. Basically the maximum permissible size is dependent on the compiler; if the compiler is 32 bit then it is simply a typedef(i.e., alias) for unsigned int but if the compiler is 64 bit then it would be a typedef for unsigned long long. The size_t data type is never negative.

strtol

The strtol library function in C converts a string to a long integer. The function works by ignoring any whitespace at the beginning of the string, converting the next characters into a long integer, and stopping when it comes across the first non-integer character.

#include <stdlib.h> // the library required to use strtol
int main() {
   char str[50] = "     90908752 rest of the string";
   char *remaining;
   long answer;
   answer = strtol(str, &remaining, 10); 
   printf("The converted long integer is %ld\n", answer);
   printf("The string part was: %s. ", remaining);
   return 0;
}

Header Files

To impose order on this situation, header files (.h) were introduced. These contain function declarations, and other information shared across files. Their name mirrors the source file that they are most closely related to, as in add.c and add.h.

The -c option tells gcc to compile to an object file (the -o option is not needed here, as the default name is *.o which is what we want (where * is everything before .c). To create an executable, gcc links the object files together.

 

Memory Size and Pointer Arithmetic

Typically

• int = 4bytes
• char = 1byte
• float = 4bytes

 

printf(“Size of int %d”, sizeof(int)); // Size of int 4

int a = 1025;
int *p;
p = &a; // pointer P points to Address a
printf("Size of int %lu \n", sizeof(int)); // Size of int 4
printf("P.addr: %p, P.val: %d \n", p, *p); // P.addr: 0x7ffee5a9a5ec, P.val: 1025
printf("P+1.addr: %p, P+1.val: %d \n", p+1, *(p+1)); // P+1.addr: 0x7ffee5a9a5f0, P+1.val: -441866720
char *c;
c = (char*)p; // typecasting
printf("Size of char %lu \n", sizeof(char)); // Size of char 1
printf("C.addr: %p, C.val: %d \n", c, *c); // C.addr: 0x7ffee5a9a5ec, C.val: 1
printf("C+1.addr: %p, C+1.val: %d \n", c+1, *(c+1)); // C+1.addr: 0x7ffee5a9a5ed, C+1.val: 4
// 1025 = 00000000 00000000 00000100 00000001
//            0        0        4        1

Pointer to Pointer

int x = 5;
int *p1 = &x;
int **p2 = &p1;
int ***p3 = &p2;
printf("*p1 %d \n", *p1);     // *p1 5
printf("*p2 %p \n", *p2);     // *p2 0x7ffeec6dd5ec (addr p1)
printf("**p2 %d \n", **p2);   // **p2 5
printf("*p3 %p \n", *p3);     // *p3 0x7ffeec6dd5e0 (addr p2)
printf("**p3 %p \n", **p3);   // **p3 0x7ffeec6dd5ec
printf("***p3 %d \n", ***p3); // ***p3 5

 

Integers and Strings

Bits and bytes

• Binary digit called bit
• Group of bits is bit string
• Group of 8 bits is byte
• Everything in computer memory is bytes
  • One byte is smallest addressable unit of data
• Bit strings have no inherent meaning
  • Meaning is imposed by software, certain hardware circuits (adder, floating point adder)

Integers representation in C

• Integers in C are represented in groups 
  • 1 byte = type char
  • 2 bytes = type short int or short
  • 4 bytes = type int
  • 8 bytes = type long int or long
  • 16 bytes = type long long int or long long
• Example of long it

00000000 00000000 00000000 00000000 00000000 00000000 100001001 …
63 55 47 39 31 23 15 …

 

Character string representation in C

• Strings are stored in memory at consecutive byte addresses and use the 00000000 byte as a terminator
• Each byte holds one ASCII representation character
• ASCII = american standard code for information interchange

 

Example of ASCII string

• The string “hello” and the hexa value of each byte for its ASCII characters and NULL 

Char string: h e l l o \n 
Byte value: 48 65 6C 6C 6F 00
Byte addr: 800 801 802 803 804 805

 

Unicode character representation

• Unicode is standard for encoding/handling of text
• Extends ASCII
• Has rules for normalization, decomposition, collation, rendering and display order
• Version 10.0, June 2017 has 136,755 characters including 1144 emoji

String functions in C

• C provides many string functions:
  • Copy string src to des

char * strcpy(char * dest, char * src)

• Length of String

int strlen(char * s)

• Appends string s2 to string s1, s1 must be large enough to hold the result

char * strcat(char * s1, char * s2)

• Compare s1 to s2 lexicographically; return an integer >, <, or = zero as s1 is larger, less than, or equal to s2

int strcmp(char * s1, char * s2)

• Find first occurrence of the substring s1 in string s2, return a pointer to the found substring

char * strstr(const char * s1, const char * s2)

• Return a duplicate of s in memory allocated usig malloc()

char * strdup(const char * s)

• See man string, man strcpy, etc

 

Implementation of strlen

char *strlen(char *src){
   int i = 0;
   while (src[i] != '\0'){
      i++;
   }
   return i;
}

 

Implementation of strcpy

char *strcpy(char *dest, char *src){
  int i = 0;
  while (src[i] != '\0'){
    dest[i] = src[i];
    // Copy character by character from src to dest
    i++;
  }
  dest[i] ='\0'; // Copy null terminator
  return dest;
}

 

Destination should point to a block of memory large enough to store the string pointed by dest

 

If, While, For, and Switch

If statement

• if (expression) { .. }
• Expression is evaluated and converted to type int
• 0 = false
• 1 = true
• { … } executed if expression is true

While statement

• while (expression) {…}
• Expression is evaluated and converted to type int
• 0 = false, 1 = true
• As long as expression is true, the statement in {…} executed repeatedly
• Each execution is called an iteration

For statement

• for (expr1; expr2; expr3) { … }
• Typically used when number of iterations is known
• expr1 is action performed before start of iteration
• expr2 is test made before each iteration
• expr3 is action performed after each iteration

Logical equivalence of while and for

• The following statements represents the same computation:

for(expr1; expr2; expr3) {...}
expr1; while(expr2) { .. expr3; }

 

Forever loops

• while(1) { … }
• for(;;) { … }

 

Switch statement

Switch (expression) {
  case const-expr: {...} break;
  case const-expr: {...} break;
…
  default: {...} break;
}

• const-expr is unique value of type int
• default is evaluated if there is no match
• break; causes immediate exit from the switch, if no break; statement then matching continues for following cases

 

Memory Allocation

Sections of a C program in memory

• An executable program in memory is organized into sections
  • TEXT = program instructions to be executed
  • RODATA = read only data, constants, eg const int
  • DATA = initialized global variables
  • BSS = uninitialized globals, they are initialized to zeroes
  • HEAP = Memory allocated when calling malloc(); extends towards higher addresses from BSS, for new objects or data structures
  • SHARED LIBRARIES = dynamic libraries, shared with other processes
  • STACK = local variables and return addresses, extends towards lower addresses

C Program sections diagram

Process address space

• Each process (executing program) has its own view of computer memory independent of other processes
• This view is called the address space of the program
• If a process modifies a byte in tits own address space, it does not moidfy the byte at the same location in the address space of another process

Example C program

Local organization of memory

• Memory organized as 1 dimensional array of bytes
  • Appears this way to CPU that access memory for R/W
  • Appears this way to the programmer
• For computer with 64bit addresses
  • Memory has locations from 0 to 2^64-1
  • Addresses range from 0x0000000000000000 to 0xFFFFFFFFFFFFFFFFFFFF in hexadecimal notation

Memory Gaps – logical versus physical organization

• Executing programs R/W using addresses of logical memory organization
• Physical computer memory is more complex
  • Capacity is limited by budget considerations
  • Some addresses are devoted to input and output rather than storage
  • So there will be gaps in physical address space
• Not all logical addresses map to physical address space
• Accessing unmapped address causes segmentation violations, like SEGV error.

Pointers

• A pointer is a variable that stores the address of another variable
• The data type of pointer and variable must match; if pointing to int variable the pointer type be of type int
• “&” Address Of Operator
  • Prefix “&” to get the address value
  • In example below we use %p format to display address in hex
• “*” Value at Address Operator
  • Prefix “*” to get address (defines the pointer)
• Print pointer values as:
  • “%lx” – long hex format instead of “%ld” as this can be negative
  • “%lud” – print with unsigned

 

 

Point Types

• Pointers must follow data type
• Can convert types
• Allows using a location as more than one type

  unsigned char *q;
  q = (unsigned char *) p;
  printf("The value of q: %d \n", *q);

Little endian and Big endian storage orders

• Consider the following C statements

int main() {
  printf("Hello endians\n");
  int i = 7; // allocates 4 bytes and initializes to 7
  unsigned char *p; // point to one byte
  p = (unsigned char *)  &i; // point to i, but which byte?
  printf("The value of p: %p \n", p);
}

• Little endian storage order
  • Store the least significant byte (the “little end”) at the lowest memory address, then
  • Store increasingly significant bytes in sequence at increasing addresses
• Big endian storage order
  • Store the most significant byte (the “big end”) at the lowest memory address, then
  • Store decreasingly significant bytes in sequence at increasing memory addresses

Arrangement of bytes in memory for example

• Data stored one byte per memory address: 100,101,102,103
• Little endian storage of 0x0005 shown on the left
• Big endian storage of 0x0005 shown on right

 

C code to determine storage order

#include <stdio.h>
int main()
{
   int i = 5;
   unsigned char *p = (unsigned char *)&i;
   if (*p == 0x05)
   {
       printf("Storage is little endian.\n");
   }
   else
   {
       printf("Storage is big endian.\n");
   }
}

Example Computers and Storage Order

• Little endian example computers
  • Intel, VAX, ARM
• Big endian example computers
  • Sparce, Motorola
• Byte order is important when exchanging data between computers
  • Assembling data into packets for the internet

#include <stdio.h>
int isLittleEndian() {
 int a = 0x05;
 char * p = (char *) &a;
 if (*p==0x05) {
   return 1;
 }
 return 0;
}
int main() {
 if (isLittleEndian()) {
   printf("Machine is Little Endian\n");
 }
 else {
   printf("Machine is Big Endian\n");
 }
}

Pointer Conversion

• Use to read/write values of any type anywhere in memory

Pointer arithmetic – adding an int to a pointer

• Pointers are byte addresses and have types: char, int, ..
• Adding 1 to a pointer of type T means to increment the pointer address so it becomes the location of the next object of type T
• When a pointer of type T and an integer are added, the integer is multiplied by the size of the type T in bytes and increment is added to the pointer

int a[10]; // Assume a[0] starts at byte address 100.
int *p; // Declare p a pointer of type integer.
p = &a[0]; // Initialize p to 100.
p = p + 1; // Since *p is of type int the constant 1 will be multiplied by sizeof(int) before adding. p now is 104 and points to a[1].
p = p + 2; // p is now 104 + 2 * sizeof(int)) = 104 + 2 * 4 = 112 which points to a[3]

 

Common pointer errors – uninitialized pointer

• Using an uninitialized pointer crashes the program with SEGV

  • int *p; // p value is NULL (0) or unknown
    *p = 10; // Program writes to invalid address and crashes

• One fix, directly initialize the pointer

  • int x; // declare x, reserving space in memory
    int *p; // p value is NULL (0) or unknown
    p = &x; // initialize p to point to location of x
    *p= 10; // use p to store 10 at location of x

• Another solution, indirectly initialize the pointer

  • int *p;
    p = (int*)malloc(sizeof(int)); // p points to allocation
    *p = 10; // Use *p
    free(p)

Common pointer errors – insufficient allocation

• Not allocating enough memory

int *array;
int n=20;
array=(int *)malloc(n * sizeof(int)); // 20*4 bytes = 80 bytes allocated
array[5]=20; // OK
array[25]=7; // Wrong. C blindly tries to assign 7 to the 25th array element, which does not exist

 

Pointers and arrays

• In C, either array notation or pointer notation can be used to refer to elements of an array
• For example, given following, a is an array of 10 elements of type int
  • int a[10];

• Also,
  • a is a pointer to the first element of the array
  • a is the same as &a[0]
  • a[0] is the same as *a
  • a[1] is the same as *(a+1)
  • a[i] is the same as *(a+i)

 

 

 

Regular Expressions

Regex using egrep

The main difference between grep and egrep is that grep is a command that allows searching content according to the given regular expression and displaying the matching lines while egrep is a variant of grep that helps to search content by applying extended regular expressions to display the machining lines.

egrep Patty regex_test.txt
Output: Patty Farnsworth

This command will return the line containing the name Patty from the document. Note that this is case-sensitive and that using “patty” instead of “Patty” will not return the line we want.

egrep [PH] regex_test.txt
Output: Patty Farnsworth

When multiple symbols are placed inside of brackets, as in this case, you are saying find lines containing “P or H”.

egrep [0-9] regex_test.txt
Output: Phone Number: 765-899-4756
4lph4num3r1c

You can search for all the numbers 0,1,2,3,4,5,6,7,8,9 by using a ‘-‘ symbol between two numbers 0 and 9. Similarly you can search for alpha characters by using a-z or A-Z for capital letters.

egrep [0-9][a-z] regex_test.txt
Output:4lph4num3r1c

It is important to see that when the brackets are used, it will only search for a single character. So in this case we are looking for any line that contains the pattern of any number immediately followed by any lower case letter.

egrep [0-9]+ regex_test.txt
Output:Phone Number: 765-899-4756

Here we see the + operator. This operator says “one or more” of the preceding character so in this case it will match any line that has 1 or more numbers consecutively.

egrep ".*" regex_test.txt
Output:Patty Farnsworth

This introduces a new symbol and operator, the “.” symbol which matches anything and the “*” operator which matches 0, 1 or more of the preceding character. So this regular expression will literally match every line with zero or more characters of any type in the document. Note here the use of double quotes surrounding the regular expression. This is necessary in this case because the arguments are processed by the shell before the command is executed. Without the quotes, the shell would replace .* with the names of all dot files of the current directory.

egrep [0-9][a-z]+[0-9] regex_test.txt
Output: 4lph4num3r1c

In this command we notice that multiple regular expressions can be combined to find complex patterns in a document. For example, in this expression we are asking for a pattern that matches a number following by at least 1 or more lower case letters followed finally by another number.

egrep [#$\+%@] regex_test.txt

In this command we are seaching for lines containing specific special characters. Note we have escaped the + symbol to prevent it from being used as a matching operator in regex and is instead treated as just the normal “+” character.

#include <stdio.h>
int main() {
  printf("Hello World!\n");
}

Note that in C, main returns an int, referred to as an exit status to the environment that invoked it.  #include is a ”preprocessor directive” that tells the compiler to include the contents of stdio.h at the beginning of the file.

gcc hello.c

This will result in an executable file with the default name: a.out . To rename the executable, use the -o option:

gcc -o hello hello.c
-std=gnu99 Compiles against the GNU C99 standard, which we will use in this course.
-g Enables debug information, allowing the use of a debugger (gdb) on the executable
-Wall Enables all warnings
-Werror Treats all warnings as errors

 

GDB

GDB is a powerful debugging tool for many programming languages. Used for C in this lab. GDB = GNU Debugger

Ways you can run GDB:

• With RUN command inside GDB terminal
• With reference to PID
• Load a coredump / corefile

Common Commands

Command Syntax	Description
break (or b) break <linenumber> break <filename>:<linenumber> break <function>	Set a “breakpoint”, or a place where the debugger will suspend execution of the program and ask for further input. Play with the arguments a little to see how flexible break is.
watch (or w) <expression>	Like break, except it will stop the program’s execution whenever the value of the given expression changes, rather than a specific point in program flow. Watchpoints can make your program run significantly slower if they have to constantly be checked, so set them carefully.
bt where	Print a “backtrace”, which lists the function call stack of the current program. Useful for determining where and why a program died.
cont (or c)	Continues program execution from where it was last stopped, by break, watch, Ctrl+C, a signal, or some other action.
help help <topic> help <command>	The bare “help” command generates a list of high-level topics which can be researched in more depth by giving arguments to the help command.
info <category>	Prints information about some part of your program, or GDB’s configuration; you may find the categories “locals”, “variables”, “functions”, and “display” useful.
next (or n)	Execute the current line of code and proceed to the next line, treating subroutine calls as one line.
step (or s)	Like next, except step enters subroutines, treating the first line of a called subroutine as the next line of code.
print (or p) <expression>	One of the most powerful commands in GDB; it is used to print the value of an arbitrary expression, such as a simple variable, a calculation, or a function call. You can use “print” to execute code that is not present in your program; e.g., running the command “print x = 6” will print the number “6”, but will also actually execute that command and set the value of x to be 6, no matter the value in the actual program.

 

 

eof