Chapter 12 Exercises: Arrays, Strings, and Data Structures

Section A: Array Access

Exercise 1. Write NASM code to access each of the following array elements. Assume the array base is in RDI and the index is in RCX:

(a) int8_t arr[100] — load arr[rcx] into RAX (sign-extend) (b) uint16_t arr[50] — load arr[rcx] into RAX (zero-extend) (c) int32_t arr[25] — load arr[rcx] into RAX (sign-extend) (d) int64_t arr[10] — load arr[rcx] into RAX (e) double arr[10] — load arr[rcx] into XMM0 (use MOVSD)

Exercise 2. Add a bounds check to each access in Exercise 1 that jumps to label .out_of_bounds if the index is invalid. Use a single comparison and the unsigned comparison trick.

Exercise 3. Given a 4×4 matrix of int64_t values stored in row-major order at base address RDI, write the NASM code to access element matrix[r][c] where row r is in RSI and column c is in RDX.

Compute the element address using: (a) IMUL (compute linear index, then multiply by 8) (b) LEA combinations (multiply r by 4 using LEA, then add c)

Exercise 4. Write a NASM function void array_sum(int64_t *arr, int64_t n, int64_t *result) that sums all elements and stores the result via the pointer.

Exercise 5. Write a NASM function void array_reverse(int64_t *arr, int64_t n) that reverses an array of int64_t in-place using two indices (one from each end, walking toward the middle).

Section B: REP String Instructions

Exercise 6. Trace through rep movsb with: - RCX = 5 - RSI = 0x1000 (source) - RDI = 0x2000 (destination) - Memory at 0x1000: [0x41, 0x42, 0x43, 0x44, 0x45]

After the instruction completes, what are the values of RSI, RDI, RCX, and the contents of memory at 0x2000?

Exercise 7. Trace through repne scasb searching for byte 0x43 ('C') in the string "ABCDEF\0": - Initial: AL = 0x43, RDI = string_base, RCX = 100 (max count)

After the instruction completes: - How many iterations ran? - What is the value of RDI relative to string_base? - What is the value of RCX? - What is ZF?

Exercise 8. The following memcpy implementation has a bug. Find it:

; memcpy(dst, src, n): RDI=dst, RSI=src, RDX=n
memcpy_buggy:
    mov rcx, rdx
    std             ; BUG: wrong direction flag
    rep movsb
    ret

Exercise 9. Write a NASM implementation of strncpy(char *dst, const char *src, size_t n) that: - Copies at most n-1 bytes from src to dst - Always null-terminates dst (if n > 0) - Pads dst with null bytes if src is shorter than n-1

Do NOT use rep movsb — write an explicit byte-at-a-time loop that handles the null terminator and padding correctly.

Exercise 10. Implement int strcmp(const char *a, const char *b) in NASM: - Returns 0 if equal - Returns positive if a > b (first differing byte) - Returns negative if a < b

Do NOT use repe cmpsb — write an explicit loop that handles null terminators correctly (stop at null in either string).

Exercise 11. Write size_t strnlen(const char *s, size_t maxlen) in NASM that returns the length of the string (not counting null), but returns maxlen if no null is found within maxlen bytes.

Section C: Structs and Data Layout

Exercise 12. Given the following struct:

struct Employee {
    uint32_t  id;        // offset 0
    uint16_t  dept_id;   // offset 4
    uint8_t   level;     // offset 6
    // 1 byte padding    // offset 7
    int64_t   salary;    // offset 8
    char     *name;      // offset 16
    struct Employee *next;  // offset 24
};                       // sizeof = 32 bytes

Write NASM code to do each of the following (assume RDI = pointer to Employee): (a) Load salary into RAX (b) Store 50000 into salary (c) Load dept_id into AX (16-bit), zero-extend to RAX (d) Load level into AL (8-bit), zero-extend to RAX (e) Load the next pointer into RBX

Exercise 13. Write a NASM function void employee_list_print_ids(Employee *head) that walks a singly-linked list of Employee structs and calls print_id(uint32_t id) (an external function) for each employee.

The next pointer is at offset 24. The id field is at offset 0.

Exercise 14. The following C struct has poor memory layout. Calculate the sizeof for each version, and write the NASM code to access the value field in each:

// Layout A (as declared):
struct RecordA {
    char  flag;      // 1 byte
    double value;    // 8 bytes (needs 8-byte alignment)
    int   count;     // 4 bytes
};

// Layout B (reordered for compactness):
struct RecordB {
    double value;    // 8 bytes
    int    count;    // 4 bytes
    char   flag;     // 1 byte
};

Section D: Linked List Operations

Exercise 15. Write a NASM function int64_t list_length(Node *head) that counts the number of nodes in a singly-linked list. Node has value at offset 0 and next at offset 8.

Exercise 16. Write a NASM function Node *list_find(Node *head, int64_t target) that returns the pointer to the first node whose value equals target, or NULL if not found.

Exercise 17. Implement a simple stack using a linked list. Write: - Node *stack_push(Node *top, int64_t value) — allocates a new node via malloc, sets its next to top, returns new head - int64_t stack_pop(Node **top_ptr) — removes the head, frees it via free, updates *top_ptr, returns the popped value

Both functions must follow the System V ABI.

Section E: Implementation Challenges

Exercise 18. Write void *memmove(void *dst, const void *src, size_t n) in NASM. Unlike memcpy, memmove must handle overlapping regions: - If dst < src, copy forward (dst + n doesn't overlap src) - If dst > src, copy backward (use STD before rep movsb, or manual backward loop) - Return dst

Exercise 19 (Challenge). Write a NASM function int64_t binary_search_arr(int64_t *arr, int64_t n, int64_t target) that implements binary search on a sorted int64_t array. Return the index if found, -1 if not found. Use no function calls.

Exercise 20 (Challenge: Doubly-Linked List). Implement a doubly-linked list node:

struct DNode {
    int64_t   value;   // offset 0
    DNode    *prev;    // offset 8
    DNode    *next;    // offset 16
};

Write: (a) DNode *dlist_insert_after(DNode *node, int64_t value) — inserts after node, returns new node (b) void dlist_remove(DNode *node) — removes node from list, updates prev/next neighbors, frees the node