C Programming

Question 1

(a) [3]

#include <stdint.h>
typedef int32_t q16_16;
#define TO_FIX(d)   ((q16_16)((d) * 65536.0 + ((d) < 0 ? -0.5 : 0.5)))
#define FROM_FIX(q) ((double)(q) / 65536.0)

• Scale factor $2^{16}=65536$. (1 mark for typedef + scale)
• Resolution $= 2^{-16} = 1/65536 \approx 1.52587890625\times10^{-5}$. (1)
• Range: $[-2^{15}, 2^{15}-2^{-16}] = [-32768, +32767.9999847...]$. (1)

(b) [5]

q16_16 fix_mul(q16_16 a, q16_16 b) {
    int64_t t = (int64_t)a * (int64_t)b;   /* full 64-bit product */
    return (q16_16)(t >> 16);              /* rescale by 2^-16 */
}

• Two Q16.16 values each up to ~$2^{31}$; product is a Q32.32 quantity needing up to ~$2^{62}$ → cannot fit in 32 bits. (2)
• Must cast before multiply; (int64_t)(a*b) would already overflow. (1)
• Signed integer overflow of int32_t is undefined behaviour (not modular wraparound; UB category: overflow of a signed integer arithmetic operation). Compiler may assume it never happens → arbitrary result. (2)

(c) [4] $g=9.81$, $h=0.5$, $gh = 4.905$.

(1 mark per correctly computed pair; rounding to nearest integer accepted.)

(d) [4] Exact: $x(1)=\tfrac12(9.81)(1)^2 = 4.905\ \mathrm{m}$. Computed $x_2 = 7.3575\ \mathrm{m}$.

• Discrepancy $= 7.3575 - 4.905 = 2.4525\ \mathrm{m}$, i.e. computed is too large. (1)

• Origin: semi-implicit Euler uses the updated velocity $v_{n+1}$ in the position update, overshooting because velocity is taken at the end of the interval; over two steps it accumulates $x = h^2 g(1+2)=...$ giving $\sum$ larger than the $\tfrac12 g t^2$ area. It is truncation/discretisation error ($O(h)$ local), NOT fixed-point rounding. (3)

  (Numeric check: semi-implicit gives $x_N = g h^2 \sum_{k=1}^N k = g h^2 N(N+1)/2$; with $N=2,h=0.5$: $9.81\cdot0.25\cdot3 = 7.3575$. ✓)

(e) [4]

• volatile forces every access to hit memory and forbids the optimiser from eliding reads/writes; using it just to defeat dead-code elimination is a misuse that destroys performance and does not make the algorithm correct — the loop isn't "dead" if its result is actually consumed. (2)
• Legitimate use: a variable aliased to a memory-mapped hardware register (e.g. reading the timer/ADC that supplies real acceleration, or a status flag set by an ISR) must be volatile so the compiler re-reads it each iteration instead of caching a stale value. (2)

Question 2

(a) [6] Per 2-bit field write the value as $2a+b$, $a,b\in\{0,1\}$; popcount of the field is $a+b$.

• $x\gg1$ shifts $a$ into the low position of the field (value $a$ there, and the high bit receives the low bit of the neighbouring field).
• Masking with 0x55...5 (binary 0101...) keeps only the low bit of each 2-bit field, isolating $a$.
• Then $x - a$ within the field $= (2a+b) - a = a+b$ = popcount. ∎ (2 for setup, 2 for shift+mask isolating $a$, 2 for subtraction giving $a+b$ with no borrow across fields because result $\le 2$ fits in 2 bits.)

(b) [5]

int popcount(uint32_t x) {
    x = x - ((x >> 1) & 0x55555555u);
    x = (x & 0x33333333u) + ((x >> 2) & 0x33333333u);
    x = (x + (x >> 4)) & 0x0F0F0F0Fu;
    return (int)((x * 0x01010101u) >> 24);
}

• After the 0x0F step, each byte holds the popcount of that byte (0–8). (2)
• Multiplying by 0x01010101 sums the four byte-counts into the top byte (each 01 broadcasts/adds the lower bytes upward; total $\le 32$ fits in 8 bits, no carry out of the top byte matters). The top byte sits at bits 24–31, so >> 24 extracts the total. (3)

(c) [4]

struct S { unsigned flags : 3; } s;
s.flags = 13;         /* 13 = 0b1101, only low 3 bits stored */

• Read back value = $13 \bmod 8 = 5$ (0b101). (2)
• Mechanism: an unsigned bit-field of width 3 holds values $0..7$; the value is reduced modulo $2^3$ on store (implementation truncates to the low 3 bits). (1)
• This is not undefined behaviour: conversion to an unsigned type is well-defined modular reduction. (1)

(d) [5]

• x << 32 where x is 32-bit uint32_t: shift count $\ge$ width of the promoted type ⇒ undefined behaviour (C rule: shift amount must be $<$ width of the (promoted) left operand type). (2)
• x << 31 is well-defined: the count 31 is $< 32$; result is x's bit 0 moved to bit 31, everything else shifted out — a defined value. (1)
• Portable "produce 0": simply 0u, or (uint32_t)0, or x & 0u. If a variable shift is desired, use (uint64_t)x << 32 then truncate — the 64-bit shift by 32 is defined. (2)

Question 3

(a) [4]

double reduce(const double *a, size_t n, double init, binop f) {
    double acc = init;
    for (size_t i = 0; i < n; i++) acc = f(acc, a[i]);
    return acc;
}
double add(double acc, double x) { return acc + x; }
/* usage: double s = reduce(arr, N, 0.0, add); */

• "Array name decays to pointer": when an array is passed as an argument, the parameter is adjusted to a pointer to its first element; the size information is lost. (2)
• sizeof a inside reduce yields sizeof(const double *) (typically 8), the pointer size — not n * sizeof(double); hence n must be passed explicitly. (2)

(b) [5]

double *make_series(size_t n) {
    double *a = malloc(n * sizeof *a);   /* == n * sizeof(double) */
    if (!a) return NULL;
    for (size_t i = 0; i < n; i++) a[i] = 1.0 / (double)(i + 1);
    return a;
}

• sizeof *a is portable regardless of double's size. (2)
• calloc zero-initialises every byte, but we overwrite all n entries immediately, so the zeroing is wasted work. (1.5)
• malloc(n * 8) hard-codes sizeof(double) == 8; on a platform where double differs (or if n * 8 overflows size_t) it under-allocates → portability/overflow bug. (1.5)

(c) [4]

• L4 reduce(p, 5, ...) after free(p): use-after-free (dangling pointer dereference). Fix: don't free before this use; or re-fetch/reallocate. (2)
• L5 second free(p): double free. Fix: free exactly once and set p = NULL after freeing (freeing NULL is a no-op). (2)

(d) [3]

• L4 → Valgrind reports "Invalid read of size 8" with "Address ... inside a block of size 40 free'd" (use-after-free). (1)
• L5 → "Invalid free() / delete / delete[]" (double free). (1)
• Segments: heap array from make_series → heap; the pointer p (local) → stack; function add (code) → text. (1)

(e) [4]

• Floating-point addition error per step is bounded by $u\cdot|\text{running sum}|$ with $u = 2^{-53}$. In natural order the running sum grows toward $\sum 1/(i+1)\approx\ln n$ while the newly added terms $1/(i+1)$ become tiny; adding a tiny term to a large sum means the small term's low bits are lost (absorbed below the ULP of the big accumulator). (2)
• Reverse order adds the smallest terms first, so partial sums stay small while the tiny terms accumulate into a comparable magnitude before the large terms dominate; fewer low bits are discarded. (1)
• Formal: total rounding error is $\lesssim u\sum_k |S_k|$ where $S_k$ are the partial sums; forward order maximises the $S_k$ at the moment small terms are added, hence larger error. Reverse order minimises $\sum|S_k|$ weighted against the small addends. (1)

[
  {"claim":"Q16.16 stored value of v1=4.905 rounds to 321462", "code":"result = round(4.905*65536)==321462"},
  {"claim":"semi-implicit Euler x2 with N=2,h=0.5,g=9.81 equals 7.3575", "code":"g