Übungen

#timestamp 20250917

install work enviroment on Linux Arch/Manjaro:

sudo pacman -S base-devel flex bison

bitwise operations -> 10% of exam!

• don't do bitwise operations on signed types
• signed type bitshift is undefined -> cast first to unsigned

common bitwise functions:

// check equality
return !(x^y);
// negative number
return ~x + 1;
// min two's complement (32bit)
return 1 << 31;
// bitwise not on 0:
// because ~0 = ~000000 = 111111 = -1
~0 = -1

#timestamp 2025-09-24

Avoid including the same file multiple times with header guards:

#ifndef HEADER_FILE
#define HEADER_FILE

// the entire header file

# endif // HEADER_FILE

system include files can be found in /usr/include

• warning options in gcc: https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html

• makefile reference/tutorial: https://cs.colby.edu/maxwell/courses/tutorials/maketutor/

• if only bitwise operations as used: compute for 1 bit -> all other bits will behave the same

• MIN_INT + MAX_INT = 111...111 (all ones) -> b^(MIN+MAX) = ~b

• shifting negative rounds to $-\mathrm{\infty }$ -> always add bias of $i^2-1$ when shifting $i$ times

#timestamp 2025-10-22

cmpq %rax, %rbx
jg X

=> jumps if %rbx > %rax

• the unusual way around!

• important jg = signed and ja = unsigned

• learn jumping instructions (logic)

• purple: return
• red: caller saved (stack pointer, base frame pointer + 2 scratch register) <- use this
• blue: caller saved (parameters) <- use this
• green: callee saved (scratch)

for callee-saved: one needs to restore value after using

pushq %r12       # save original value
...
popq %r12        # restore original value

inline assembly:

int a=10, b;
__asm__ ("movl %1, %%eax; movl %%eax, %0;"
		:"=r"(b) // output operands, optional
		:"r"(a)  // input operands, optional
		:"%eax"  // list of clobbered registers, optional
);

or named:

int a=10, b;
__asm__ ("movl %[in], %%eax; movl %%eax, %[out];"
		: [out] "=r"(b) // output operands, optional
		: [in]  "r"(a)  // input operands, optional
		:"%eax"  // list of clobbered registers, optional
);

of course, it can be simplified:

int a=10, b;
__asm__ ("movl %[in], %[out]"
		: [out] "=r"(b) // output operands, optional
		: [in]  "r"(a)  // input operands, optional
);

if no variable changes, use volatile to prevent the compile from deleting it!

__asm__ volatile ("movb %bh (%eax)\n\t"); // \n\t for multiple instructions needed, here optional

#timestamp 2025-11-05

symbols

• global: functions, global variables

• local: static vars,

• strong: function, initalized globals

• weak: unitalized globals

• multiple strong symbols are not allowed (linker error)

• s.t. we know which one to use (1x strong, 1x weak -> use strong)
  - this happens even if the weak/strong are not of same type!!

-> modern C: always mark extern (and -fno-common flag) s.t. there is no arbitrary choosing

libraries

static libraries (.a)

• multiple obj files in one file
• when compiling, always put static libraries at end

dynamic libraries

append library path:

export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:$PWD

• static and dynamic libraries use the same amount of memory (since dynamic -> headers included)
• #include "sth.c" -> preprocessor copies file

32-bit PC-relative displacement

A 4-byte signed number stored in the instruction that tells the CPU how many bytes to jump forward/backwards from the next instruction. (PC = Program Counter = %rip on x86)

e.g.

400406: e8 f5 00 00 00 callq 400500 <swap>

• current instruction: e8 (call) at 0x400406
• next instruction (where the %rip pointer points to): 0x400406 + 5 = 0x40040b
• displacement (signed, little-endian): f5 00 00 00 -> 0xf5
  • jump to %rip + 0xf5 -> 0x400500

CPU doesn't know the symbol name (swap), it only sees the displacement

This comes from how the program is created:

1. the compiler doesn't know swap's final address -> writes instruction + placeholder, e.g. e8 00 00 00 00 and adds a relocation entry
2. the linker assigns final addresses to all functions, computes displacement:
   • displacement = next_address (%rip) - next_instruction_address
3. the CPU executes callq at 0x400406, reads displacement, jumps to right place
4. disassembly: objump read instruction, computes target address and names after the symbol table ->
   • callq 400500 <swap>

#timestamp 2025-11-26

• read-read: can be parallelised
• read-write: too
• write-write: can be problematic, but this too
• write-read: -> problem

• lower bound: CPE is bound by critical path
• tell the compiler that for the lifetime of the restrict-annotated pointer it will be the only pointer used to access the underlying memory
  • compiler does not check, programmer responsible exection (no run-time checks that it is the only pointer)